Problem Statement

You are given a sequence a = (a_1, \dots, a_N)a=(a1,…,aN) of length $N$ consisting of integers between $1$ and $N$.
Find the number of pairs of integers $i,j$ that satisfy all of the following conditions:

• $1\le i<j\le N$
• \min(a_i, a_j) = imin(ai,aj)=i
• \max(a_i, a_j) = jmax(ai,aj)=j

Constraints

• 2 \leq N \leq 5 \times 10^52≤N≤5×105
• 1 \leq a_i \leq N \, (1 \leq i \leq N)1≤ai≤N(1≤i≤N)
• All values in input are integers.

$N$a_1a1$\dots$a_NaN