A. Uma lacuna

Time limit: 4000 msMemory limit: 256 MB

Uma coleção está organizada em uma sequência de $n$ números inteiros distintos. Um trecho é interessante quando falta exatamente um inteiro entre seu menor e seu maior número. A ordem dos números no trecho não importa para essa condição.

Conte os pares de índices $(l,r)$ , com $1 \le l \le r \le n$ , para os quais o trecho $a_l,\ldots,a_r$ é interessante. O inteiro ausente deve estar estritamente entre o mínimo e o máximo do trecho.

Input

A primeira linha contém $n$ ( $1 \le n \le 200000$ ). A segunda contém $n$ inteiros distintos $a_1,\ldots,a_n$ ().

Output

Imprima a quantidade de trechos interessantes.

Samples

Sample 1

Input

4
1 3 2 5

Output

Os trechos são $[1,3]$ , $[3,2,5]$ e $[1,3,2,5]$ . No primeiro falta ; nos outros falta .