AlgoLiga 2018

Uwaga: Limit pamięci w tym zadaniu to 16Mb.

Bajtomir zaczął niedawno grać na giełdzie. Wykonał już kilka udanych transakcji i kilka nieudanych. Jak każdy kto gra na giełdzie, Bajtomir postanowił skorzystać z różnego rodzaju programów analizujących spadki i wzrosty akcji oraz obligacji. Po długich rozważaniach stwierdził, że przydałby mu się jeszcze jeden program - taki, który mierzyłby poziom wahania danej akcji. Poziom wahania dla ciągu cen danej akcji określony jest ilością elementów jego najdłuższego podciągu, takiego że jego kolejne wyrazy naprzemian rosną i maleją. Przykładami takich podciągów są <1, 4, 2, 3> lub <9, 4, 6>. Mając ów program Bajtomir sam zdecyduje czy akcję o dużym poziomie wahania opłaca się kupić podczas spadku jej wartości by następnie ją sprzedać gdy jej cena wzrośnie, czy lepiej poczekać aż owa akcja się ustabilizuje. Jako że masz dług u Bajtomira, Tobie przypadło napisanie owego programu.

Wejście

Wejście składa się z liczby testów t (t < 1001). Pierwsza linia każdego testu zawiera liczbę n (0 < n ≤ 5*10⁶) oznaczającą ilość kolejnych cen danej akcji. Druga i ostatnia linia każdego testu zawiera n cen danej akcji (w bajtalarach) z przedziału 1..10⁹. Żadne dwie kolejne ceny nie są takie same - akcja albo traci, albo zyskuje na wartości.

Wyjście

Dla każdego testu stopień wahania danej akcji.

Przykład

Wejście:
3
5
1 2 3 2 1
6
3 2 1 3 2 1
6
1 2 1 2 1 2

Wyjście:
3
4
6

Wyjaśnienie przykładu:

W pierwszym teście najdłuższe możliwe podciągi to: 1-2-1, 1-3-2, 1-3-1, 2-3-2, 2-3-1.

W drugim teście: 3-2-3-2, 3-2-3-1, 3-1-3-2, 3-1-3-1.

W trzecim teście jest tylko jeden najdłuższy podciąg będący całym ciągiem.