Let us make it possible to quickly determine whether \(x\) satisfies the conditions.

First, it is clearly necessary that \(x_i \leq x_{i+1}+1\).

Index \(j\) is said to be a record as seen from \(i\) if and only if \(i+1 \leq j \leq i+N-1\) and \(\max_{i \leq k \leq j} p_k = p_j\) holds. Note that \(j=i\) is excluded. By subtracting \(1\) from each \(x_i\), we consider \(x_i\) to be the number of records as seen from \(i\).

Suppose the maximum value among \(p_1,\ldots,p_N\) is \(p_m\). Let the smallest record as seen from \(m\) be \(N+c\). When \(x_m=0\), set \(c=m\) for convenience.

Now, let us consider the number of records as seen from \(N\). First, for \(i\) satisfying \(N+1 \leq i < N+c\), it is fine for this to be a record. Considering \(i\) satisfying \(N+c \leq i\), we see that if \(x_{i-N} > x_{i-N+1}\) holds, then \(i\) must not be included as a record.

If the number of record candidates obtained in this way is less than \(x_N\), then no \(p\) satisfies the condition.

Once \(m\) is fixed, we can find the maximum possible value of the corresponding \(c\). This can be done by looking at \(p_m,p_{m-1},\ldots\) in order and stopping at the moment when the number of times the sequence did not increase becomes exactly \(x_m\).

Considering the condition around \(x_N\), we see that it is best for \(c\) to be as large as possible. So, let us try all candidates for \(m\), find the maximum value of \(c\), and determine whether the constraint on \(x_N\) can be satisfied for it.

This is a determination of a necessary condition, but actually it can be shown to also be sufficient. Suppose we actually take \(m\) that maximizes \(c\). Then, as records as seen from \(N\), we first use all candidates that are at least \(N+c\). The fact that there are at most \(x_N\) candidates that are at least \(N+c\) follows from the fact that \(c\) is maximized. Now, we just need to choose some (random) elements within \(N+1 \leq i < N+c\) to serve as records. From there, we look at \(i=N-1,N-2,\ldots\) in order. From the value of \(x_i\), we can compute the relative ordering between the record as seen from \(i+1\) and \(p_i\). Using the condition that “when \(x_i>x_{i+1}\), \(N+i\) is not included as a record,” we can construct \(p_i\) without contradiction, and it follows that the determination regarding \(x\) is both necessary and sufficient.

This determination can be done in \(O(N)\) by looking at \(x_N,x_{N-1},\ldots\) in order. At the step when we finish looking at \(x_i\), we need to maintain the following three pieces of information:

• The value of \(x_i\);
• The count of \(j\) (\(N+i \leq j\)) that could be records as seen from \(N\);
• The minimum count of \(x_k \leq x_{k+1}\) (\(k < i\)) that will be needed from here on before reaching \(c\), if we adopt \(i \leq j \leq N\) as \(m\).

By directly incorporating this into a DP, we can count \(x_i\). Doing this naively takes \(O(N^5)\), which is sufficiently fast.

Sample Solution (C++)