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: ASM32-GCC ASM64 MAWK BC C-CLANG NCSHARP CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY3 R RACKET RUST SCM qobi CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Pochodzenie:ALGOLIGA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.