C. Os Extremos da Moldura

Time limit: 3000 msMemory limit: 256 MB

Uma galeria expõe $n$ quadros em linha. O quadro $i$ tem altura $a_i$ , e todas as alturas são distintas.

Um visitante escolhe dois quadros em posições $l<r$ e considera toda a sequência de quadros entre eles, incluindo as duas extremidades. Essa escolha forma uma moldura especial quando o quadro mais baixo e o quadro mais alto da sequência estão justamente nas duas extremidades, em qualquer ordem.

Formalmente, a escolha é especial quando

\{a_l,a_r\}=\left\{\min_{l\le i\le r}a_i,\ \max_{l\le i\le r}a_i\right\}.

Conte quantas escolhas $(l,r)$ formam uma moldura especial.

Input

A primeira linha contém $n$ . A segunda linha contém as $n$ alturas $a_1,\ldots,a_n$ .

Output

Imprima a quantidade de pares $(l,r)$ válidos.

Samples

Sample 1

Input

3
3 1 2

Output

Os pares adjacentes são válidos; a sequência inteira não tem ambos os extremos nas pontas.

Sample 2

Input

4
1 2 3 4

Output

Somente pares consecutivos são válidos, pois sempre existe um valor intermediário entre as alturas dos extremos de intervalos maiores.

Sample 3

Input

2
100 9

Output

Os dois únicos quadros são necessariamente o maior e o menor.