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_31_08 - Dwa ciągi

Dzielimy ciąg liczb całkowitych an na dwa ciągi w taki sposób, że pierwszy zawiera początkowe i wyrazów (1 ≤ in) 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..107].

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

Dodane przez:Marcin Kasprowicz
Data dodania:2017-01-06
Limit czasu wykonania programu:1s-1.200s
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.