G - ΣШX Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 600 点

問題文

長さ N の非負整数列 A = (A_1, \dots, A_N) が与えられます。

1 \leq l \leq r \leq N を満たす整数の組 (l, r) に対する \mathrm{mex}({A_l, \cdots, A_r}) の総和を求めてください。

ここで、\mathrm{mex}({A_l, \cdots, A_r}) は A_l, \cdots, A_r に含まれない最小の非負整数を表します。

制約

  • 1 \leq N \leq 3 \times 10^5
  • 0 \leq A_i \leq N
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \cdots A_N

出力

答えを出力せよ。

入力例 1

3
1 2 0

出力例 1

5

以下の 6 個の値の総和である 5 が答えです。

  • \mathrm{mex}({A_1}) = \mathrm{mex}({1}) = 0
  • \mathrm{mex}({A_1,A_2}) = \mathrm{mex}({1,2}) = 0
  • \mathrm{mex}({A_1,A_2,A_3}) = \mathrm{mex}({1,2,0}) = 3
  • \mathrm{mex}({A_2}) = \mathrm{mex}({2}) = 0
  • \mathrm{mex}({A_2,A_3}) = \mathrm{mex}({2,0}) = 1
  • \mathrm{mex}({A_3}) = \mathrm{mex}({0}) = 1

入力例 2

6
2 1 0 2 1 4

出力例 2

31

以下の 21 個の値の総和である 31 が答えです。

  • \mathrm{mex}({A_1}) = \mathrm{mex}({2}) = 0
  • \mathrm{mex}({A_1,A_2}) = \mathrm{mex}({2,1}) = 0
  • \mathrm{mex}({A_1,A_2,A_3}) = \mathrm{mex}({2,1,0}) = 3
  • \mathrm{mex}({A_1,A_2,A_3,A_4}) = \mathrm{mex}({2,1,0,2}) = 3
  • \mathrm{mex}({A_1,A_2,A_3,A_4,A_5}) = \mathrm{mex}({2,1,0,2,1}) = 3
  • \mathrm{mex}({A_1,A_2,A_3,A_4,A_5,A_6}) = \mathrm{mex}({2,1,0,2,1,4}) = 3
  • \mathrm{mex}({A_2}) = \mathrm{mex}({1}) = 0
  • \mathrm{mex}({A_2,A_3}) = \mathrm{mex}({1,0}) = 2
  • \mathrm{mex}({A_2,A_3,A_4}) = \mathrm{mex}({1,0,2}) = 3
  • \mathrm{mex}({A_2,A_3,A_4,A_5}) = \mathrm{mex}({1,0,2,1}) = 3
  • \mathrm{mex}({A_2,A_3,A_4,A_5,A_6}) = \mathrm{mex}({1,0,2,1,4}) = 3
  • \mathrm{mex}({A_3}) = \mathrm{mex}({0}) = 1
  • \mathrm{mex}({A_3,A_4}) = \mathrm{mex}({0,2}) = 1
  • \mathrm{mex}({A_3,A_4,A_5}) = \mathrm{mex}({0,2,1}) = 3
  • \mathrm{mex}({A_3,A_4,A_5,A_6}) = \mathrm{mex}({0,2,1,4}) = 3
  • \mathrm{mex}({A_4}) = \mathrm{mex}({2}) = 0
  • \mathrm{mex}({A_4,A_5}) = \mathrm{mex}({2,1}) = 0
  • \mathrm{mex}({A_4,A_5,A_6}) = \mathrm{mex}({2,1,4}) = 0
  • \mathrm{mex}({A_5}) = \mathrm{mex}({1}) = 0
  • \mathrm{mex}({A_5,A_6}) = \mathrm{mex}({1,4}) = 0
  • \mathrm{mex}({A_6}) = \mathrm{mex}({4}) = 0

入力例 3

25
2 2 1 2 2 0 2 2 2 1 2 2 2 0 2 2 2 2 1 2 2 2 2 0 2

出力例 3

624

Score : 600 points

Problem Statement

You are given a length-N sequence of non-negative integers A = (A_1, \dots, A_N).

Find the sum of \mathrm{mex}({A_l, \cdots, A_r}) over all pairs of integers (l, r) satisfying 1 \leq l \leq r \leq N.

Here, \mathrm{mex}({A_l, \cdots, A_r}) denotes the smallest non-negative integer not contained in A_l, \cdots, A_r.

Constraints

  • 1 \leq N \leq 3 \times 10^5
  • 0 \leq A_i \leq N
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Output the answer.

Sample Input 1

3
1 2 0

Sample Output 1

5

The answer is 5, the sum of the following 6 values.

  • \mathrm{mex}({A_1}) = \mathrm{mex}({1}) = 0
  • \mathrm{mex}({A_1,A_2}) = \mathrm{mex}({1,2}) = 0
  • \mathrm{mex}({A_1,A_2,A_3}) = \mathrm{mex}({1,2,0}) = 3
  • \mathrm{mex}({A_2}) = \mathrm{mex}({2}) = 0
  • \mathrm{mex}({A_2,A_3}) = \mathrm{mex}({2,0}) = 1
  • \mathrm{mex}({A_3}) = \mathrm{mex}({0}) = 1

Sample Input 2

6
2 1 0 2 1 4

Sample Output 2

31

The answer is 31, the sum of the following 21 values.

  • \mathrm{mex}({A_1}) = \mathrm{mex}({2}) = 0
  • \mathrm{mex}({A_1,A_2}) = \mathrm{mex}({2,1}) = 0
  • \mathrm{mex}({A_1,A_2,A_3}) = \mathrm{mex}({2,1,0}) = 3
  • \mathrm{mex}({A_1,A_2,A_3,A_4}) = \mathrm{mex}({2,1,0,2}) = 3
  • \mathrm{mex}({A_1,A_2,A_3,A_4,A_5}) = \mathrm{mex}({2,1,0,2,1}) = 3
  • \mathrm{mex}({A_1,A_2,A_3,A_4,A_5,A_6}) = \mathrm{mex}({2,1,0,2,1,4}) = 3
  • \mathrm{mex}({A_2}) = \mathrm{mex}({1}) = 0
  • \mathrm{mex}({A_2,A_3}) = \mathrm{mex}({1,0}) = 2
  • \mathrm{mex}({A_2,A_3,A_4}) = \mathrm{mex}({1,0,2}) = 3
  • \mathrm{mex}({A_2,A_3,A_4,A_5}) = \mathrm{mex}({1,0,2,1}) = 3
  • \mathrm{mex}({A_2,A_3,A_4,A_5,A_6}) = \mathrm{mex}({1,0,2,1,4}) = 3
  • \mathrm{mex}({A_3}) = \mathrm{mex}({0}) = 1
  • \mathrm{mex}({A_3,A_4}) = \mathrm{mex}({0,2}) = 1
  • \mathrm{mex}({A_3,A_4,A_5}) = \mathrm{mex}({0,2,1}) = 3
  • \mathrm{mex}({A_3,A_4,A_5,A_6}) = \mathrm{mex}({0,2,1,4}) = 3
  • \mathrm{mex}({A_4}) = \mathrm{mex}({2}) = 0
  • \mathrm{mex}({A_4,A_5}) = \mathrm{mex}({2,1}) = 0
  • \mathrm{mex}({A_4,A_5,A_6}) = \mathrm{mex}({2,1,4}) = 0
  • \mathrm{mex}({A_5}) = \mathrm{mex}({1}) = 0
  • \mathrm{mex}({A_5,A_6}) = \mathrm{mex}({1,4}) = 0
  • \mathrm{mex}({A_6}) = \mathrm{mex}({4}) = 0

Sample Input 3

25
2 2 1 2 2 0 2 2 2 1 2 2 2 0 2 2 2 2 1 2 2 2 2 0 2

Sample Output 3

624