No.1525 Meximum Sum
タグ : / 解いたユーザー数 42
作問者 : Chippppp / テスター : MtSaka
問題文
集合 $\{0, 1, \dots, N - 1\}$ の要素を並び替えた順列 $A = (A_1, A_2, \dots, A_N)$ が与えられます.
$\displaystyle \sum_{l = 1} ^ {N} \sum_{r = l} ^ {N} mex(A_{l}, A_{l+1}, \dots, A_{r})$
を求めてください.ただし,$mex(S)$ を $S$ に含まれない最小の非負整数とします.
入力
$N$ $A_1 \quad A_2 \quad \dots \quad A_N$
出力
$\displaystyle \sum_{l = 1} ^ {N} \sum_{r = l} ^ {N} mex(A_{l}, A_{l+1}, \dots, A_{r})$
を一行に出力してください.
また,最後に改行を出力してください.
サンプル
サンプル1
入力
3
0 2 1
出力
5
$l = 1$ のとき,$mex(0) + mex(0, 2) + mex(0, 2, 1) = 5$
$l = 2$ のとき,$mex(2) + mex(2, 1) = 0$
$l = 3$ のとき,$mex(1) = 0$
よって,$5 + 0 + 0 = 5$ です.
サンプル2
入力
10
9 6 8 5 1 0 3 2 4 7
出力
112
サンプル3
入力
15
12 9 4 6 5 2 0 1 7 13 10 14 8 11 3
出力
197
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。