G. Σex · AC 题库

JPRSプログラミングコンテスト2026#2 （AtCoder Beginner Contest 470）

Σex

AtCoder

⌀ 2097

原题

← E→

ΣexAI (CI翻译)

Problem Statement

题目描述

AI (CI翻译)

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

给定一个长度为 $N$ 的非负整数序列 $A = (A_1, \dots, A_N)$ 。AI (CI翻译)

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$ .

求满足 $1 \leq l \leq r \leq N$ 的所有整数对 $(l, r)$ 对应的 $\mathrm{mex}({A_l, \cdots, A_r})$ 之和。AI (CI翻译)

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

其中， $\mathrm{mex}({A_l, \cdots, A_r})$ 表示未包含在 $A_l, \cdots, A_r$ 中的最小非负整数。AI (CI翻译)

Constraints

约束条件

AI (CI翻译)

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

$1 \leq N \leq 3 \times 10^5$
$0 \leq A_i \leq N$
所有输入值均为整数。

AI (CI翻译)

Input

输入格式

AI (CI翻译)

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

输入通过标准输入按以下格式给出：AI (CI翻译)

N
A_1 A_2 \cdots A_N

N
A_1 A_2 \cdots A_N

AI (CI翻译)

Output

输出格式

AI (CI翻译)

Output the answer.

输出答案。AI (CI翻译)

样例

Input #1

3
1 2 0

Output #1

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$

Input #2

6
2 1 0 2 1 4

Output #2

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$

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

Output #3

题目信息

题号

abc470_g

所属比赛

JPRSプログラミングコンテスト2026#2 （AtCoder Beginner Contest 470）

时间限制

3 s

内存限制

1024 MB

题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。