配点 : 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
5P 的是 (0,2,1) 和 (0,1,2) 的 2 有一条街。每个要找到的值是 5,6 ,所以5 。
入力例 3
10 1 -1 -1 4 -1 -1 3 -1 8 -1
出力例 3
19