No.696 square1001 and Permutation 5

レベル : / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 11
作問者 : square1001square1001 / テスター : PulmnPulmn

1 ProblemId : 2125 / 出題時の順位表

問題文

2168 年, John と Brus は JOI に出場しており, 彼らは本選で全完し優勝しました. なので, John と Brus は JOI 春合宿で 4 位以内を取り, IOI の日本代表になると予想されていました.

しかし, 残念ながら 2 人とも春合宿で失敗してしまい, 同じ点数で 4 位を取ってしまいました. JOI 春合宿は 4 日間ありますが, 4 日間すべて同じ点数でした. 本選も両方全完していて同じ点数なので, なんと「最後の決闘」で代表選手を決めることになってしまいました!


最後の決闘では, 次のような問題が出されました. John と Brus は, 最後の望みをかけて, この問題を解こうとしました.

  • $1, 2, 3, \cdots, N$ の順列 $p = (p_1, p_2, p_3, \cdots, p_N)$ が与えられます. $p$ は $1, 2, 3, \cdots, N$ の順列の中で辞書順で何番目でしょうか?

John と Brus はこの問題の解法が分かり, 実装をして, コードのバグを直しました. 2 時間が経ち, そして, 両方がこの問題を正解しました. しかし, Brus より John の方が 1 秒だけ早く提出していたのです!

したがって, John が日本代表に選ばれました. かわいそうな Brus, 残念ながら IOI 日本代表に選ばれず, なんと彼は刑務所に入れられてしましました!


あなたは John と Brus のストーリーを聞きました. さて, この問題を 2 時間以内に解いて彼らより実力が高いことを証明してみましょう!


問題文の元ネタ:SRM 719 Div1 Hard - RedemptionOfMatthew99

入力

$N$
$p_1 \ p_2 \ p_3 \ \cdots \ p_N$
  • $1$ 行目には, 整数 $N$ が与えられる.
  • $2$ 行目には, $N$ 個の整数 $p_1, p_2, p_3, \cdots, p_N$ が空白区切りで与えられます.

出力

$p$ が $1, 2, 3, \cdots, N$ の順列の中で辞書順で何番目なのかを, $1$ 行で出力してください.

制約

すべての入力データは以下の制約を満たす.

  • $1 \le N \le 100 \ 000$.
  • $1 \leq p_i \leq N \ (1 \leq i \leq N)$
  • $p_i \neq p_j \ (1 \leq i < j \leq N)$

サンプル

サンプル1
入力
3
2 3 1
出力
4

これより辞書順で小さい $1, 2, 3$ の順列は, $(1, 2, 3), (1, 3, 2), (2, 1, 3)$ の $3$ つなので, $(2, 3, 1)$ は辞書順で $4$ 番目です.

サンプル2
入力
5
3 1 5 4 2
出力
54
提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。