No.1371 交換門松列・松
タグ : / 解いたユーザー数 31
作問者 :
夕叢霧香(ゆうむらきりか)
定義
3つの要素から成る数列 $v = (a_1,a_2,a_3)$ が次の条件を満たす時、$v$は門松列であると言い伝えられています。
- $a_1,a_2,a_3$ は全て異なる
- 3つの要素のうち $a_2$ が最も大きい、あるいは最も小さい
さらに、$n$ 個の要素 ( ただし $3\le n$ ) から成る数列 $w = (a_1,...,a_n)$ が
どの連続した 3 つの要素を取り出しても門松列であるとき
$w$ は門松列列であると言います。
問題文
長さ $N$ の順列が与えられます。
不思議なことに、この順列は何者かによって既に門松列列に並び替えられていました。
雪小寺さんは、ある2つの要素を交換しても門松列列のままにできるかどうか疑問に思いました。
$i$ 番目と $j$ 番目の要素を交換しても門松列列であるような、$i$ と $j$ ( $i\lt j$ ) の組合せの個数を出力してください。
入力
$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)$
入力はすべて整数である。
$A$ は門松列列である。
出力
$(i,j)$ としてありえる組合せの個数を出力してください。
最後に改行してください。
サンプル
サンプル1
入力
6 1 4 2 5 3 6
出力
7
次の 7 通りです。
- 1 番目と 3 番目を交換する。
- 1 番目と 5 番目を交換する。
- 2 番目と 4 番目を交換する。
- 2 番目と 5 番目を交換する。
- 2 番目と 6 番目を交換する。
- 3 番目と 5 番目を交換する。
- 4 番目と 6 番目を交換する。
サンプル2
入力
5 1 3 2 5 4
出力
2
$(i,j)$ としてありえるのは (1,3), (2,5) の2通りですね。
サンプル3
入力
15 5 10 6 9 7 12 1 14 8 13 11 15 3 4 2
出力
37
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。