AlgoLiga 2018

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 <p_1, p_2, ..., p_n> (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 <p_i, p_j, p_k>, ż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<t<=10. Pojedynczy test to liczba 0<n<=10⁵ oraz, po spacji, n-permutacja, która stanowi sekwencję bajtokwasów Megabajtusa pospolitusa.

Wyjście

Dla każdego testu należy wypisać odpowiedź w oddzielnej linii. Odpowiedzią jest liczba możliwych gatunków Trylobajtów, które pochodzą od danego Megabajtusa pospolitusa.

Przykład

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

Wyjście:
1
3

Wyjaśnienie do przykładu:

W drugim teście Megabajtus pospolitus ma sekwencję bajtokwasów <4, 2, 3, 5, 1>. Liczba wszystkich monotonicznych podciągów 3-elementowych tej permutacji to 3 i są to: <4, 2, 1>, <4, 3, 1> oraz <2, 3, 5>. Mamy zatem trzy gatunki Trylobajtów.