問題文

長さ 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
• 入力は全て整数

入力例 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