Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_12_08 - Bajtomir na giełdzie

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*106) 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..109. Ż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.


Dodane przez:Piotr Kąkol
Data dodania:2013-11-22
Limit czasu wykonania programu:0.5s-1.75s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
Pochodzenie:ALGOLIGA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.