AlgoLiga 2018

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 ≤ 10⁵) oznaczająca liczbę drzew przy drodze, w wierszu drugim podanych jest n liczb całkowitych a_i, (1 ≤ a_i ≤ 10⁹) 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