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_10_03 - Bajtokwasy

dnaBajtoccy 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<=105 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.


Dodane przez:Adam Bąk
Data dodania:2013-09-11
Limit czasu wykonania programu:1s-2s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:ALGOLIGA
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.