\(x\) が条件を満たすかどうかの判定を高速に行えるようにします．

まず明らかに \(x_i \leq x_{i+1}+1\) が必要です．

index \(j\) が \(i\) から見た record であるとは，\(i+1 \leq j \leq i+N-1\) かつ \(\max_{i \leq k \leq j} p_k = p_j\) を満たすこととします． \(j=i\) を除外していることに注意してください． 各 \(x_i\) から \(1\) ずつ引くことで，\(x_i\) は \(i\) から見た record の個数であるとします．

\(p_1,\ldots,p_N\) の中での最大値が \(p_m\) だったとします． \(m\) から見た record のうち最小のものを \(N+c\) とおきます． \(x_m=0\) のときは便宜上 \(c=m\) とします．

ここで，\(N\) から見た record の個数を考えましょう． まず，\(N+1 \leq i < N+c\) を満たす \(i\) に関しては，これが record であっても問題はありません． \(N+c \leq i\) を満たす \(i\) について考えると，\(x_{i-N} > x_{i-N+1}\) を満たしている場合，\(i\) が record に含まれてはいけないことが分かります．

こうして得られた record の候補数が \(x_N\) 未満である場合，条件を満たす \(p\) は存在しないことになります．

\(m\) を決めると，それに対応する \(c\) としてありうる最大値を求めることができます． これは \(p_m,p_{m-1},\ldots\) と見ていって，増加しなかった回数がちょうど \(x_m\) になったタイミングで止まればよいです．

\(x_N\) 周りの条件を考えると，\(c\) はできるだけ大きい方がよいとわかります． そこで，\(m\) の候補を全部試し，\(c\) の最大値を求め，それに対して \(x_N\) の制約を満たせるかどうか判定することを考えます．

これは必要条件の判定ですが，実は十分でもあることが示せます． 実際に \(c\) を最大化する \(m\) をとったとします．このとき，\(N\) から見た record として，まず \(N+c\) 以上の候補を全部利用します． \(N+c\) 以上の候補の個数が \(x_N\) 以下であることは，\(c\) を最大化していることから従います． あとは \(N+1 \leq i < N+c\) 内の要素を適当に（本当に任意に）選んで record とすればよいです． そこからは \(i=N-1,N-2,\ldots\) と順にみていきます．\(x_i\) の値から，\(i+1\) から見た record と \(p_i\) の相対的な大小関係が計算できます． \(x_i>x_{i+1}\) では \(N+i\) は record に入らない，という条件から矛盾なく \(p_i\) を構成することができて，\(x\) に関する判定が必要十分であることが従います．

この判定は，\(x_N,x_{N-1},\ldots\) と順にみていくことで \(O(N)\) でできます． \(x_i\) を見終えた段階で保持すべき情報は以下の \(3\) つです．

• \(x_i\) の値
• \(N\) から見た record としてありうる \(j\) (\(N+i \leq j\)) の個数
• \(i \leq j \leq N\) を \(m\) として採用した場合，\(c\) に到達するまでにこの先必要な \(x_k \leq x_{k+1}\) (\(k < i\)) の個数の最小値．

これをそのまま DP に乗せることで，\(x_i\) の数え上げができます． 愚直にやると \(O(N^5)\) で，十分高速です．

解答例(C++)