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_20_11 - Wycinka drzew

Wycinka drzew

Nowo wybrany wójt gminy Monotoniczne, Stanisław Nierosnący wydał swoje pierwsze rozporządzenie. Zarządził, że w miejscowościach Łąka Stała, Pionki Rosnące i Pionki Malejące należy uporządkować drzewa stojące wzdłuż dróg lokalnych. W tym celu w gminie zatrudniono nową osobę, zajmie się tym Jan Niestały, specjalista od wszystkiego. Rozporządzenie mówi, że wzdłuż każdej z dróg należy pozostawić tylko te drzewa, których wysokości będą monotoniczne na całej długości. Pierwszy tydzień Jan poświęcił na mierzenie, teraz musi zdecydować, które z drzew należy wyciąć. Jan chciałby pozostawić jak najwięcej drzew, kombinuje na wszystkie możliwe sposoby, ale nie jest pewien, czy nie można tego zrobić lepiej. Postanowił problem przekazać gminnemu informatykowi. Znając wysokości kolejnych drzew wzdłuż drogi, musisz obliczyć, ile najmniej drzew należy wyciąć, aby pozostałe tworzyły ciąg monotoniczny.

Wejście
W pierwszym wierszu wejścia znajduje się liczba przypadków testowych d (d ≤ 100). Każdy przypadek opisany jest w dwóch wierszach. W pierwszym wierszu podana jest liczba n (1 ≤ n ≤ 105) oznaczająca liczbę drzew przy drodze, w wierszu drugim podanych jest n liczb całkowitych ai, (1 ≤ ai ≤ 109) oznaczających wysokości kolejnych drzew wzdłuż drogi.

Wyjście
Dla każdego przypadku testowego należy wypisać najmniejszą liczbę drzew jakie trzeba wyciąć, aby pozostałe tworzyły ciąg monotoniczny.

Przykład

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

Wyjście
0
2


Dodane przez:Mariusz Śliwiński
Data dodania:2014-12-17
Limit czasu wykonania programu:1s
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.