\(\mathrm{mex}(\lbrace P_l,\ldots,P_r\rbrace)=\min(N,P_1,\ldots,P_{l-1},P_{r+1},\ldots,P_N)\) が成り立ちます．よって，答えは \(A[l:r]\) に含まれない \(-1\) 以外の要素の最小値 \(m\) （なければ \(m=N\)）と \(-1\) の個数 \(c\) に依存します．

\(A[l:r]\) に含まれる \(-1\) の個数を \(d\) ，\(A\) に含まれない \(0\) 以上 \(N\) 未満の整数の集合を \(S=\{s_1,s_2,\ldots,s_k\}\ (s_1<s_2<\dots<s_k)\)，\(s_{k+1}=N\) とすると，答えは \(c!d!\displaystyle \sum_{i=1}^{k+1}\min(m,s_i)\times \left(\binom{k-i+1}{c}-\binom{k-i}{c}\right)\) です．

すべての \(c,m\) に対する答えをまとめて \(O(N^2)\) で前計算しておくことで，クエリあたり \(O(1)\) で答えを求められます．