Opgave

Je krijgt een figuur zoals hieronder: van links naar rechts gezien gaat het zwart op en neer. Het doel is een figuur te bekomen die (ook weer van links naar rechts gezien) niet meer daalt, dus enkel stijgt of gelijk blijft. Gevraagd: wat is het minimaal aantal vakjes dat zwart gekleurd moet worden om dat te bekomen?



Deze figuur laat zien - met de grijze vakjes - dat 6 vakjes volstaan: meer is niet nodig.

Invoer

De eerste regel van de invoer bevat het aantal testgevallen. Per testgeval volgt dan één regel met een aantal natuurlijke getallen, van elkaar gescheiden door één enkele spatie. Het eerste getal op elke regel geeft aan hoeveel getallen er nog volgen. De volgende getallen geven de hoogte aan van de zwarte balken. De getallen overeenkomend met het voorbeeld hiervoor zijn

8 1 4 3 2 5 3 6 5

omdat er 8 zwarte balken zijn, waarvan de eerste hoogte 1 heeft, de tweede hoogte 4, de derde hoogte 3, enzovoort.

Voorbeeldinvoer:

3
2 1 2
2 2 1
5 5 4 3 2 1

Uitvoer

De uitvoer bestaat uit één regel per testgeval. Elke regel bestaat uit twee gehele getallen, van elkaar gescheiden door één enkele spatie. Het eerste getal is de index van het testgeval (startend bij 1) en het tweede getal is het minimum aantal blokjes dat moet worden ingekleurd zodat de figuur enkel stijgt of gelijk blijft.

Voorbeelduitvoer:

1 0
2 1
3 10