No.1031 いたずら好きなお姉ちゃん
レベル : / 実行時間制限 : 1ケース 3.500秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 55
作問者 :
Rho
/ テスター :
Thistle
タグ : / 解いたユーザー数 55
作問者 :
Rho
/ テスター :
Thistle
問題文最終更新日: 2020-05-29 20:26:06
問題文
Shinobuは長さ $N$ の順列 $p$ を持っています。
ある日Shinobuが昼寝をしているとき、Isamiがこの順列にいたずらをしてしまいました。そのいたずらでは以下の操作が行われました。
- 順列 ${p}$ から長さ$2$以上の区間$[l,r]$ を選ぶ。
- 区間$[l,r]$の中で最大の要素 $p_{max}$ と最小の要素 $p_{min}$ を選び、2つの位置を交換する。
入力
$N$ $p_1\ p_2\ ... p_N$
入力は全て整数である。
$1 \leq N \leq 10^5$
$1 \leq p_i \leq N (1 \leq i \leq N)$
$p_i ≠ p_j (i ≠ j)$
出力
操作後の順列の通り数を出力してください。
最後に改行してください。
サンプル
サンプル1
入力
3 2 1 3
出力
2
Isamiが区間$[1,2]$を選んだ場合、操作後の数列は${1,2,3}$となります。
区間$[1,3]$を選んだ場合、操作後の数列は${2,3,1}$となります。
区間$[2,3]$を選んだ場合、操作後の順列は${2,3,1}$となります。
よって、出力する答えは $2$ となります。
サンプル2
入力
5 1 2 3 4 5
出力
10
サンプル3
入力
8 1 7 3 2 5 8 6 4
出力
11
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。