No.1525 Meximum Sum
Problem Statement
You are given a permutation $A = (A_1, A_2, \dots, A_N)$ obtained by rearranging the elements of the set $\{0, 1, \dots, N - 1\}$.
$\displaystyle \sum_{l = 1} ^ {N} \sum_{r = l} ^ {N} mex(A_{l}, A_{l+1}, \dots, A_{r})$
Find the value above. Here, $mex(S)$ denotes the smallest non-negative integer not contained in $S$.
Input
$N$ $A_1 \quad A_2 \quad \dots \quad A_N$
Output
$\displaystyle \sum_{l = 1} ^ {N} \sum_{r = l} ^ {N} mex(A_{l}, A_{l+1}, \dots, A_{r})$
Print the value above on a single line.
Also, print a newline at the end.
Sample
Sample 1
Input
3
0 2 1
Output
5
For $l = 1$, $mex(0) + mex(0, 2) + mex(0, 2, 1) = 5$
For $l = 2$, $mex(2) + mex(2, 1) = 0$
For $l = 3$, $mex(1) = 0$
Therefore, the answer is $5 + 0 + 0 = 5$.
Sample 2
Input
10
9 6 8 5 1 0 3 2 4 7
Output
112
Sample 3
Input
15
12 9 4 6 5 2 0 1 7 13 10 14 8 11 3
Output
197
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。