2. A nech sú moje hady v suchu

Viete čo mačky naozaj nemajú rady? Vodu. A viete aké zviera nemá rado mačky? Predsa hady. Ty, ako správny hadonoš¹, ktorý má svoje hady veľmi rád, by si chcel svojim hadom dopriať pokoj od mačiek. Po daždi sa to dá veľmi jednoducho. Na niektorých miestach Tvojho pozemku po daždi ostane stáť voda, a to sú miesta, kam môžeš dať svojich hadov a budú mať pokoj od mačiek. Teraz by si ale chcel zistiť, koľko vodou zatopených políčok ostane na tvojom pozemku po daždi.

Úloha

Pre jednoduchosť uvažujme, že Tvoj pozemok je dvojrozmerný. Má iba šírku a výšku. Každé miesto na Tvojom pozemku je súvislý stĺpec zeme od výšky \(0\) až po výšku terénu v danom mieste. Pôda na Tvojom pozemku je nepriepustná a vždy naprší dostatočné množstvo vody aby zaplnilo všetky miesta kde môže ostať voda. Vypíš súčet plôch tých políčok Tvojho pozemku, kde po napršaní ostane voda.

Formát vstupu

Na prvom riadku vstupu je číslo \(n\) označujúce šírku pozemku. Platí \(1\leq n \leq 50\,000\). Nasleduje jeden riadok obsahujúci \(n\) medzerou oddelených celých čísel \(v_i\), výšky terénu v poradí zľava doprava. Platí, že \(0 \leq i < n\) a \(0 \leq v_i \leq 220\,000\)

Formát výstupu

Vypíšte jedno číslo, počet políčok, ktoré po daždi ostanú zatopené vodou. Nezabudnite za číslom vypísať znak konca riadku.

Obmedzenia

Sú \(4\) sady vstupov po \(2\) body. Platia v nich nasledovné obmedzenia:

Všimnite si že vstupné a výstupné údaje sa nemusia zmestiť do 32 bitovej premennej, odporúčame preto použiť 64 bitovú premennú (napr. long long v C++).

Príklad

Input:

12
0 1 0 2 1 0 1 3 2 1 2 1

Output:

6

Označme X zem a O vodu a pre lepšiu ilustráciu - nulovú výšku terénu. V takejto krajine sa po napršaní udrží 6 vody:

       X
   XOOOXXOX
 XOXXOXXXXXX 
------------

Input:

3
1 1 1

Output:

0

Tu sa nemá kde zachytiť voda a teda žiadne políčko neostane po daždi zatopené.