No.696 square1001 and Permutation 5
タグ : / 解いたユーザー数 18
作問者 :


問題文
2168 年, John と Brus は JOI に出場しており, 彼らは本選で全完し優勝しました. なので, John と Brus は JOI 春合宿で 4 位以内を取り, IOI の日本代表になると予想されていました.
しかし, 残念ながら 2 人とも春合宿で失敗してしまい, 同じ点数で 4 位を取ってしまいました. JOI 春合宿は 4 日間ありますが, 4 日間すべて同じ点数でした. 本選も両方全完していて同じ点数なので, なんと「最後の決闘」で代表選手を決めることになってしまいました!
最後の決闘では, 次のような問題が出されました. John と Brus は, 最後の望みをかけて, この問題を解こうとしました.
の順列 が与えられます. は の順列の中で辞書順で何番目でしょうか?
John と Brus はこの問題の解法が分かり, 実装をして, コードのバグを直しました. 2 時間が経ち, そして, 両方がこの問題を正解しました. しかし, Brus より John の方が 1 秒だけ早く提出していたのです!
したがって, John が日本代表に選ばれました. かわいそうな Brus, 残念ながら IOI 日本代表に選ばれず, なんと彼は刑務所に入れられてしましました!
あなたは John と Brus のストーリーを聞きました. さて, この問題を 2 時間以内に解いて彼らより実力が高いことを証明してみましょう!
入力
行目には, 整数 が与えられる. 行目には, 個の整数 が空白区切りで与えられます.
出力
制約
すべての入力データは以下の制約を満たす.
.
サンプル
サンプル1
入力
3 2 3 1
出力
4
これより辞書順で小さい
サンプル2
入力
5 3 1 5 4 2
出力
54
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。