No.1525 Meximum Sum
タグ : / 解いたユーザー数 36
作問者 :
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もしくは右上の雲マークをクリックしてアカウントを作成してください。