Cyclic Rotation to Strictly Increasing Sequence

Given a permutation a of length \(n\), consider any contiguous subarray \(b = [a_l, a_{l+1}, \dots, a_r]\) (with \(1 \le l \le r \le n\)). You are allowed to perform the following operation on \(b\): choose an index \(i\) (\(1 \le i \le k\), where \(k = r-l+1\)) and rotate \(b\) to obtain

[ [b_i, b_{i+1}, \dots, b_k, b_1, b_2, \dots, b_{i-1}] ]

The value \(f(b)\) is defined as the minimum number of operations needed to turn \(b\) into a strictly increasing sequence. If it is impossible to achieve a strictly increasing sequence via any rotation, then \(f(b)=0\). (Note that if \(b\) is already strictly increasing, then \(f(b)=0\).)

Your task is to compute

[ \sum_{l=1}^{n} \sum_{r=l}^{n} f([a_l, a_{l+1}, \dots, a_r]) ]

Observation:
Since the only allowed operation is a cyclic rotation, note that any sequence \(b\) can be rotated into a strictly increasing order if and only if it is cyclically sorted – that is, when viewing \(b\) as a circle there is exactly one place where the order "drops". In other words, if \(b\) is already strictly increasing, then \(f(b)=0\); if there is exactly one index \(p\) (with \(l \le p b_{p+1}\) and in addition \(b_r .

It turns out that for any contiguous subarray \(b\), \(f(b)\) is either \(0\) or \(1\), and your goal is to sum these values over all subarrays of \(a\>.

inputFormat

The first line contains a single integer \(n\) representing the length of the permutation.

The second line contains \(n\) space-separated distinct integers \(a_1, a_2, \dots, a_n\) which form a permutation of \(1, 2, \dots, n\).

outputFormat

Output a single integer: the sum of \(f(b)\) over all contiguous subarrays \(b\) of \(a\).

sample

2
2 1

1