A tester’s solution.

---

[0] Notations

For integers \(i\) and \(x\) \((1 \le i \le N^2,\ 1\leq x \le S)\), let \(\mathrm{front}(i,x)\) denote the smallest \(j\) such that \(A_{j}=x,\ i < j\) (if no such \(j\) exists, let \(\mathrm{front}(i,x)=\infty\)). After preprocessing in \(O(N)\) time, it can be found in \(O(\log N)\) time per query.

For a sequence of integers of length \(n\), \(X=(X_1,\ X_2,\ \dots,\ X_n)\), let \(f(X)\) denote the largest \(s\) that satisfies the following.

• Every sequence \(Y\) of positive integers totaling \(s\) is a subsequence of \(X\).

---

[1] “Distributing” DP

Let \(dp_s\) be the smallest \(i\) such that \(f((A_1,\ A_2,\ \dots,\ A_i))=s\). (it can be seen that such an \(i\) always exists by considering a sequence of positive integers ending with \(x=1\)).

Consider a sequence of positive integers totaling \(s\) whose last term is \(x\). It will be a subsequence of \((A_1,\ A_2,\ \dots,\ A_i)\) when \(\mathrm{front}(dp_{s-x},x) \leq i\), so we have \(\displaystyle dp_s=\max_{1\leq x \leq s} \mathrm{front}(dp_{s-x},x)\).

These \(dp_s\) can be found by a distributing DP where one initializes with \(dp_s=0\ (1\leq s \leq S)\) and lets \(dp_{s+x}\leftarrow \max(dp_{s+x},\ \mathrm{front}(dp_s, x))\) for \(s=0,\ 1,\ \dots,\ S-1\) in this order.

---

[2] Optimization by divide-and-conquer

Let us optimize the distributing DP above by divide-and-conquer.

Consider finding \(dp_{l},\ dp_{l+1},\ \dots,\ dp_{r}\). Let \(m=\lfloor \frac{l+r}{2} \rfloor\) and we will do the following in order:

• recursively find \(dp_{l},\ dp_{l+1},\ \dots,\ dp_{m-1}\),
• distribute the contributions from \(dp_{l},\ dp_{l+1},\ \dots,\ dp_{m-1}\) to \(dp_{m},\ dp_{m+1} ,\ \dots,\ dp_r\),
• recursively find \(dp_{m},\ dp_{m+1},\ \dots,\ dp_{r}\).

It is enough to process the second part fast.

First, when distributing the contributions from \(dp_{l},\ dp_{l+1},\ \dots,\ dp_{m-1}\) to \(dp_{m},\ dp_{m+1} ,\ \dots,\ dp_r\), we only have to consider \(x=1,\ 2,\ \dots,\ r-l\).

Let us think of what to do for each \(x\). From the monotonicity of \(dp_s\) with respect to \(s\), there is no need to distribute for \(s\) such that \(\mathrm{front}(dp_{s},x)\) is less than \(dp_{m-1}\). Thus, we only have to consider \(s\) such that \(\mathrm{front}(dp_s,\ x)=\mathrm{front}(dp_{m-1},\ x)\). These \(s\) form an interval.

Thus, for each \(x\), we find \(m_x\), the smallest \(s\ (l \leq s \leq m-1)\) such that \(\mathrm{front}(dp_s,\ x)=\mathrm{front}(dp_{m-1},\ x)\), and let \(dp_{s+x}\leftarrow \max(dp_{s+x},\ \mathrm{front}(dp_{m-1},\ x))\) for each \(m_x \leq s \leq m-1\).

This can be done in \(O(\log S)\) for each \(x\) by using a segment tree that supports ranged chmax and single-element access.

Implementing the above solves the problem in \(O(N+S\log{S}(\log S + \log N))\) time.