Wstęp do programowania w C++

Dzielimy ciąg liczb całkowitych a_n na dwa ciągi w taki sposób, że pierwszy zawiera początkowe i wyrazów (1 ≤ i ≤ n) natomiast drugi pozostałe wyrazy. Należy tak dobrać indeks i aby po usunięciu możliwie najmniejszej liczby wyrazów z obydwu ciągów, pierwszy był rosnący, natomiast drugi malejący.

Uwagi do zadania

• dopuszczamy sytuację, że jeden z ciągów nie ma wyrazów, wtedy ten drugi  podciąg musi być rosnący lub malejący
• jeden lub dwa ciągi mogą być jednowyrazowe, np. dla ciągu 1 2 2 otrzymujemy 1 2 i 2, w tej sytuacji nie usuwamy żadnego wyrazu.

Wejście

W pierwszym wierszu jedna liczba t określająca liczbę zestawów danych (nie więcej niż 100).

Każdy zestaw testowy składa się z dwóch wierszy. W pierwszym wierszu jedna liczba n, która określa liczbę wyrazów w ciągu (nie więcej niż 100 000).

W drugim wierszu n liczb, każda mieści się w przedziale [0..10⁷].

Wyjście

Dla każdego zestawu testowego należy określić najmniejszą liczbę wyrazów do usunięcia, tak aby ciągi (ciąg) spełniały kryteria zadania.

Przykład

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

Wyjście:
0
1