No.1525 Meximum Sum

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

No.1525 Meximum Sum

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 43
作問者 :

Chippppp / テスター :

MtSaka

3 ProblemId : 6102 / 自分の提出

問題文最終更新日: 2021-05-29 00:26:56

問題文

集合 ${0, 1, \dots, N - 1}$ の要素を並び替えた順列 $A = (A_{1}, A_{2}, \dots, A_{N})$ が与えられます．
$\sum_{l = 1}^{N} \sum_{r = l}^{N} m e x (A_{l}, A_{l + 1}, \dots, A_{r})$
を求めてください．ただし， $m e x (S)$ を $S$ に含まれない最小の非負整数とします．

入力

 $N$ 
 $A_{1} A_{2} \dots A_{N}$

1 \leq N \leq 2 \times 10^{5}

A

は集合

{0, 1, \dots, N - 1}

の要素を並び替えた数列である．

入力は全て整数

出力

$\sum_{l = 1}^{N} \sum_{r = l}^{N} m e x (A_{l}, A_{l + 1}, \dots, A_{r})$
を一行に出力してください．また，最後に改行を出力してください．

サンプル

サンプル1

入力

3
0 2 1

出力

$l = 1$ のとき， $m e x (0) + m e x (0, 2) + m e x (0, 2, 1) = 5$
$l = 2$ のとき， $m e x (2) + m e x (2, 1) = 0$
$l = 3$ のとき， $m e x (1) = 0$
よって， $5 + 0 + 0 = 5$ です．

サンプル2

入力

10
9 6 8 5 1 0 3 2 4 7

出力

サンプル3

入力

15
12 9 4 6 5 2 0 1 7 13 10 14 8 11 3

出力

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。

yukicoder

No.1525 Meximum Sum

問題文

入力

出力

サンプル

サンプル1

入力

出力

サンプル2

入力

出力

サンプル3

入力

出力