問題一覧 > 通常問題

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

レベル : / 実行時間制限 : 1ケース 3.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 57
作問者 : Rho / テスター : Thistle
4 ProblemId : 4171 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-05-29 20:26:06

問題文

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

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

入力

N
p1 p2 ...pN

入力は全て整数である。
1≤N≤105
1≤pi≤N(1≤i≤N)
pi≠pj(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もしくは右上の雲マークをクリックしてアカウントを作成してください。