POLSKI SPOJ

Bajtoccy genetycy zbadali już dokładnie sekwencje bajtokwasów nicienia Bajtorhabditis elegans i muszki Bajtophila melanogaster. Teraz przyszedł czas na Trylobajty. Okazało się, że sekwencje bajtokwasów wszystkich gatunków tych stworzeń pochodzą w pewnym sensie od sekwencji bajtokwasów innego zwierzątka - Megabajtusa pospolitusa. Naukowcy udowodnili, że mając sekwencję bajtokwasów (która jest n-permutacją) tego drugiego możemy z łatwością ustalić sekwencje bajtokwasów wszystkich gatunków Trylobajtów. Proces ten polega na znalezieniu wszystkich takich podciągów tej sekwencji , że i < j < k oraz p_i < p_j < p_k lub p_i  > p_j > p_k. Odkrycie zatem jest naprawdę godne podziwu. Problem tylko polega na tym, aby ustalić ile tak właściwie tych podciągów możemy otrzymać. Cóż, do tego potrzeba sprawnego informatyka, zatem naukowcy proszą Cię o pomoc.

Wejście

Wejście rozpoczyna liczba testów 0. Pojedynczy test to liczba 05 oraz, po spacji, n-permutacja, która stanowi sekwencję bajtokwasów Megabajtusa pospolitusa.

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

Wyjście:
1
3