AT_pakencamp_2023_day1_l Range Mex Sum Min

给定一个长度为 $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, x_2, \ldots, x_n$ 当中的最小非负整数。

输入按以下格式，从标准输入给出。 > $N$ $A_1$ $A_2$ $ \ldots $ $A_N$

请输出答案。

### 样例解释 1 $\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 可以选择的 $P$ 依次为 $(0,2,1)$ 和 $(0,1,2)$ 共 $2$ 种。对于这两种，目标值分别为 $5, 6$，因此答案是 $5$。 ### 数据范围 - $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$ - 所有输入均为整数。 由 ChatGPT 5 翻译