Good Pair Painting

A permutation a of length \(n\) is given. Consider the following painting process on the permutation (which is viewed as an array). Initially you may choose any one element \(a_i\) and color it white. Afterwards, in each step you extend the white block as follows: if the current contiguous white block is from index \(L\) to \(R\) (initially \(L=R=i\)), then among the candidates (if they exist) \(a_{L-1}\) (to the left) and \(a_{R+1}\) (to the right), you color white the number with the smaller value. Clearly after \(n\) steps the whole permutation gets colored white.

For any pair of indices \((i,j)\) with \(1 \le i \le j \le n\) we define the following: Let \(f(i,j)\) be the step at which \(a_j\) gets colored when the process is started with \(a_i\) (with \(f(i,i)=1\)). We say that the pair \((i,j)\) is a good pair if there exists a step \(k\) such that when the process is started with \(a_i\), \(a_j\) becomes white at the \(k\text{-th}\) step, and when the process is started with \(a_j\), \(a_i\) becomes white at the \(k\text{-th}\) step as well.

Your task is to compute the number of good pairs.

Observation. Note that when \(i=j\) the pair is trivially good. For \(i<j\) one may prove that \(f(i,j)=j-i+1\) (i.e. the white block extends step‐by‐step in the unique direction toward the other index) if and only if the extension is not diverted by elements outside the interval \([i,j]\). In particular, if we work 1–indexed and use 0–indexed arrays in the code then a necessary and sufficient condition for \((i,j)\) with \(i<j\) to be good is:

[ \begin{array}{ll} \text{if } i>1:& \max{a_{i+1},a_{i+2},\ldots,a_j} < a_{i-1},\[6mm] \text{if } j<n:& \max{a_i,a_{i+1},\ldots,a_{j-1}} < a_{j+1}. \end{array} ]

Then, the answer equals the number of pairs \((i,j)\) (with \(1\le i\le j\le n\)) satisfying the above conditions (where the boundary conditions are taken as automatically true).

inputFormat

The first line contains an integer \(n\) \((1 \le n \le 3000)\), the length of the permutation. The second line contains \(n\) distinct integers \(a_1,a_2,\ldots,a_n\) representing the permutation of \(1,2,\ldots,n\).

outputFormat

Output a single integer, the number of good pairs.

sample

3
2 1 3

5