No.1031 いたずら好きなお姉ちゃん

レベル : / 実行時間制限 : 1ケース 3.500秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 47
作問者 : RhoRho / テスター : ThistleThistle
3 ProblemId : 4171 / 出題時の順位表
問題文最終更新日: 2020-05-29 20:26:06

問題文

Shinobuは長さ $N$ の順列 $p$ を持っています。
ある日Shinobuが昼寝をしているとき、Isamiがこの順列にいたずらをしてしまいました。そのいたずらでは以下の操作が行われました。

  • 順列 ${p}$ から長さ$2$以上の区間$[l,r]$ を選ぶ。
  • 区間$[l,r]$の中で最大の要素 $p_{max}$ と最小の要素 $p_{min}$ を選び、2つの位置を交換する。
順列を復元したいShinobuのために、Isamiが操作した後の順列の数として考えられるものの個数を求めてください。

入力

$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もしくは右上の雲マークをクリックしてアカウントを作成してください。