No.1031 Mischievous Big Sister
Rho
ThistleProblem Statement
Shinobu has a permutation $p$ of length $N$.
One day, while Shinobu was taking a nap, Isami played a prank on this permutation. In the prank, the following operation was performed.
- Choose an interval $[l,r]$ of length $2$ or more from the permutation ${p}$.
- Choose the maximum element $p_{max}$ and the minimum element $p_{min}$ in the interval $[l,r]$, and swap their two positions.
Input
$N$ $p_1\ p_2\ ... p_N$
All inputs are integers.
$1 \leq N \leq 10^5$
$1 \leq p_i \leq N (1 \leq i \leq N)$
$p_i ≠ p_j (i ≠ j)$
Output
Output the number of possible permutations after the operation.
Print a newline at the end.
Sample
Sample 1
Input
3 2 1 3
Output
2
If Isami chooses the interval $[1,2]$, the sequence after the operation is ${1,2,3}$.
If she chooses the interval $[1,3]$, the sequence after the operation is ${2,3,1}$.
If she chooses the interval $[2,3]$, the permutation after the operation is ${2,3,1}$.
Therefore, the answer to output is $2$.
Sample 2
Input
5 1 2 3 4 5
Output
10
Sample 3
Input
8 1 7 3 2 5 8 6 4
Output
11
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。