← 返回题目列表

AtCoder · pakencamp_2023_day1_l

L. 范围 Mex 总和 Min

中文机器翻译题面 查看原题

配点 : 500 点

問題文

长度 N 整数序列 给出了 A 。满足以下条件 考虑 (0,1,\ldots,N-1) 的排列 对于 P 。

  • 1 \le i \le N , A_i \neq -1 然后, A_i = P_i

这样的排列 找出下面 P 的最小可能值。 表示

  • \displaystyle \sum_{i=1}^N \sum_{j=i}^N \mathrm{mex}(P_i,P_{i+1},\ldots,P_j)

但是, \mathrm{mex}(x_1,x_2,\ldots,x_n) 是 x 中不包含的最小非负整数。

制約

  • 1 \leq N \leq 2\times 10^5
  • 1 \le i \le N , A_i = -1 这个类型的变量里只能放入 0 \le A_i < N
  • 1 \le i < j \le N , A_i, A_j \neq -1 如果 可以认为 A_i \neq A_j
  • 所有输入均为整数

入力

输入将以以下形式从标准输入给出。

N
A_1 A_2 \ldots A_N

出力

输出答案。


入力例 1

3
0 2 1

出力例 1

5

\mathrm{mex}(0)+\mathrm{mex}(0,2)+\mathrm{mex}(0,2,1)+\mathrm{mex}(2)+\mathrm{mex}(2,1)+\mathrm{mex}(1)=1+1+3+0+0+0=5 。


入力例 2

3
0 -1 -1

出力例 2

5
P 的是 (0,2,1) 和 (0,1,2) 的 2 有一条街。每个要找到的值是 5,6 ,所以5 。

入力例 3

10
1 -1 -1 4 -1 -1 3 -1 8 -1

出力例 3

19