Ocean View egy kis város a tengerparton. Egyetlen utcája a Döbbenetes utca, amely a tengerparttól a hegyek felé vezet, és az utca házai 1-től N-ig vannak számozva. (1 van a tengerparton.)

A lakók szeretnének kilátni a tengerre, de sajnos vannak házak, amelyek eltakarják mások elől a kilátást. Ház A eltakarja a kilátást B elől, ha A < B és A legalább olyan magas, mint B.

Belefáradva az állandó panaszáradatba, Ocean View kormányzója úgy döntött, hogy megoldja a problémát és kedvenc kormányzati eszközéhez, az erőszakhoz folyamodik. Parancsot ad néhány ház lerombolására, hogy a többiek kilátását biztosítsa. Persze nem akar túl sok házat lerombolni, mert fél, hogy esetleg forradalom törne ki, ezért minimalizálni szeretné a lebontandó házak számát. 

Írjunk programot, ami megadja, hogy legkevesebb hány ház lebontásával lehet elérni, hogy a megmaradt házak lakói kilássanak a tengerre.

A bemenet első sora a tesztesetek T számát adja meg (T <= 100). Ezután T teszteset jön, két-két sorban. Az első sor mindig a házak számát tartalmazza (1 <= N <= 1000), a második pedig az N ház magasságát (1 és 1000 közötti egészek, szóközzel elválasztva).

A kimenet egyetlen sorába a minimálisan lebontandó házak számát kell írni.

Bemenet	Kimenet
4 4 1 4 3 3 5 3 4 6 7 10 4 4 3 2 1 5 4 5 6 1 7	Case #1: 2 Case #2: 0 Case #3: 3 Case #4: 1

A feladat forrása: Google Code Jam 2013 - veteran competition

Algoritmusok: dinamikus programozás

megoldás