TURING - FIIT STU

Úloha 1-1: Paprika

Jakubko dostal vreckové. Namiesto toho, aby ho len tak minul, však dostal geniálny nápad. Čo keby začal podnikať?

Na trhu predávajú papriku. Jakubko si všimol, že cena papriky sa každý deň mení. Zároveň sa mu podarilo vypočítať odhad cien papriky pre nasledovných N dní. Teraz už len potrebuje zistiť, ktoré dni má papriku kúpiť a ktoré ju predá. Keďže ešte nevie, či jeho odhad je správny, povedal si, že vždy bude mať nakúpenú najviac jednu papriku, teda pred tým než kúpi ďalšiu papriku, musí tú predchádajúcu predať.

Vstup: Na prvom riadku vstupu je celé číslo T, ktoré vyjadruje počet scenárov. Pre každý scenár nasleduje samostatný riadok. Na každom z týchto riadkov je najprv uvedené celé číslo N a potom N čísel, ktoré vyjadrujú odhad cien papriky na nasledovných N dní.

Výstup: Pre každý scenár vypočítajte maximálny zisk, ktorý Jakubko dokáže dosiahnuť. Môžete predpokladať, že počiatočné vreckové bude stačiť na nákup akejkoľvek drahej papriky. Toto vreckové sa do výsledku nezapočítava.

Ukážka vstupu:
1
2 1 3
Výstup pre ukážkový vstup:
2