3. Gigantický Legoland

Vitajte, vitajte! Počula som, že v Legolande ste prvý raz. Nevadí, vysvetlím vám, ako to tu funguje. Je to vskutku celkom jednoduché. Vidíte? Tam pred vami v jednom rade sú všetky atrakcie, ktoré tu máme. Určite ich chcete všetky navštíviť. Ale počkať, ešte som neskončila. Čo prosím? Že zem je hrboľatá? To nie, to len stojíte na legokocke. Ľahko viete skočiť na inú. Samozrejme, skočiť možte len na kocku, ktorá je hneď vľavo, vpravo, hore alebo dole voči vašej momentálnej kocke. Takto si budete hopkať aj medzi našími atrakciami. A teda, medzi dvoma atrakciami vždy prejdete Manhattanskú vzdialenosť. A teraz k pravidlám vašej návštevy. Sú len dve. Prvé: atrakcie, ktoré navštívite musia tvoriť súvislý úsek. Druhé: (pre dobro rodičov, ktorí sa snažia prejsť z atrakcie A do atrakcie B, bez toho, aby prešli okolo atrakcie C (vraj to ušetrí veľa detských sĺz), pre každú trojicu z úseku musí platiť, že súčet vzdialeností medzi dvoma dvojicami sa nemôže rovnať vzdialenosti medzi treťou dvojicou. To je celé. Jednoduché, však? Vyberte si úsek atrakcií, ktoré chcete navštíviť a do toho! Počet úsekov, z ktorých si môžete vybrať je… Vlastne, nemôžem robiť všetkú robotu za vás. Určite na to zvládnete prísť sami.

Úloha

Dané je pole \(R\) s \(n\) atrakciami: \(r_{1}, r_{2}, ..., r_{n}\). Súradnice \(i\)-tej atrakcie sú \((i, r_{i})\). Vzdialenosť medzi atrakciou \(a\) = \((a, r_{a})\) a atrakciou \(b\) = \((b, r_{b})\) je: \(v(a,b)\) = \(|a - b| + |r_{a} - r_{b}|\). Vašou úlohou je nájsť počet súvislých úsekov pre ktoré platí, že v nich neexistuje trojica atrakcií i, j, k, pre ktoré platí \(v(i,j) = v(i,k) + v(k,j)\).

Formát vstupu

V prvom riadku vstupu je číslo \(n\) udávajúce počet atrakcií v poli. V prvej sade platí \(1 \leq n \leq 30\) a v druhej sade platí \(1 \leq n \leq 2 \cdot 10^5\). V nasledujúcom riadku je \(n\) čísel reprezentujúcich ypsilonové súradnice atrakcií \(r\): \(r_{1}, r_{2}, ...,r_{n}\). Pre obe sady platí \(1 \leq r_i \leq 10^9\).

Formát výstupu

Vypíš jeden riadok a v ňom jedno celé číslo: počet súvislých úsekov, ktoré môžte v Legolande navštíviť.

Príklad

Input:

4
3 5 2 4

Output:

10

V prvom prípade je jedno, ktorý úsek vyberiete. Všetky sú dobré. že prejdeme okolo tretej. Všetky súvislé úseky sú dobré.

Input:

5
7 10 2 10 7

Output:

12

V druhom prípade si môžte všimnúť, že okolo úseku [r_1, r_2, r_3, r_4] nemôžete prejsť, lebo by sa nám mohlo stať, že pri prechode od prvej atrakcie k štvrtej by ste prešli okolo druhej.