No.1371 Swap Kadomatsu Sequence: Matsu
タグ : / 解いたユーザー数 31
作問者 :
夕叢霧香(ゆうむらきりか)
Definition
A sequence of 3 elements $v = (a_1,a_2,a_3)$ is, according to tradition, called a Kadomatsu sequence when $v$ satisfies the following conditions.
- $a_1,a_2,a_3$ are all distinct
- Among the 3 elements, $a_2$ is the largest or the smallest
Furthermore, when a sequence $w = (a_1,...,a_n)$ of $n$ elements (where $3\le n$) is such that
any 3 consecutive elements taken from it form a Kadomatsu sequence,
$w$ is called a Kadomatsu sequence sequence.
Problem Statement
You are given a permutation of length $N$.
Mysteriously, this permutation has already been rearranged into a Kadomatsu sequence sequence by someone.
Yukikodera-san wondered whether it could remain a Kadomatsu sequence sequence even after swapping some two elements.
Output the number of pairs $i$ and $j$ ( $i\lt j$ ) such that the sequence is still a Kadomatsu sequence sequence after swapping the $i$-th and $j$-th elements.
Input
$N$ $A_1\ \ldots\ A_N$
$5 \le N \le 2\times 10^5$
$1 \le A_i \le N$
$A_i \neq A_j\ (i\neq j)$
All inputs are integers.
$A$ is a Kadomatsu sequence sequence.
Output
Output the number of possible pairs $(i,j)$.
Print a newline at the end.
Sample
Sample 1
Input
6 1 4 2 5 3 6
Output
7
The following 7 ways are possible.
- Swap the 1st and 3rd elements.
- Swap the 1st and 5th elements.
- Swap the 2nd and 4th elements.
- Swap the 2nd and 5th elements.
- Swap the 2nd and 6th elements.
- Swap the 3rd and 5th elements.
- Swap the 4th and 6th elements.
Sample 2
Input
5 1 3 2 5 4
Output
2
The possible $(i,j)$ are the 2 pairs (1,3), (2,5).
Sample 3
Input
15 5 10 6 9 7 12 1 14 8 13 11 15 3 4 2
Output
37
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。