\(\displaystyle \sum_{i=1}^N \sum_{j=i}^N \mathrm{mex}(P_i,P_{i+1},\ldots,P_j)=S\) とします。

\(A_i=-1\) となる \(i\) が存在しないとき、\(S\) の値を高速に求めることを考えます。

\(B_i\) を \(A_j=i\) が成り立つ \(j\) の値とします。ここで、\(C_i\) を \(i \leq \mathrm{mex}(P_l,P_{l+1},\ldots,P_r)\) を満たす整数 \((l,r)\) の組の個数としたとき、\(C_{N+1}=0\) であることに注意すると以下の式が成り立ちます。

• \(S=\displaystyle \sum_{i=0}^N i(C_i-C_{i+1})=\displaystyle \sum_{i=1}^{N}C_i\)

\(1 \leq i \leq N\) のとき、\(C_{i} = \min(B_0,B_1,\dots,B_{i-1})\times (N-\max(B_0,B_1,\dots,B_{i-1})+1)\) であることに注意すると、結局のところ \(S\) の値は以下の値と等しいことが分かります。

• \(\displaystyle \sum_{i=0}^{N-1}{ \min(B_0,B_1,\dots,B_{i})\times (N-\max(B_0,B_1,\dots,B_{i})+1)}\)

この値を最小化することを考えます。まず、\(A_i=-1\) となる \(i\) が \(1\) 個以下の場合は簡単なので、そうでない場合を考えます。

このとき、\(0,1,\dots,N-1\) のうち \(A\) に登場していない値であって、\(i\) 番目に小さいものを \(x_i\) とします。また、\(A_i=-1\) となる \(i\) であって、\(j\) 番目に小さいものを \(y_j\) とします。このとき、\(P\) のうち以下の条件のいずれかを満たすものの中に \(S\) の値が最小となるものが含まれることが証明できます。ここで、\(M\) を \(A_i=-1\) である \(i\) の個数とします。

• \(P_{y_1}=x_1,P_{y_M}=x_2\)
• \(P_{y_1}=x_2,P_{y_M}=x_1\)

よって、以上の \(2\) 通りについて \(S\) の値を計算し、そのうち小さい方を求めれば良いです。よって、この問題を \(O(N)\) で解くことができました。