[0] Notations

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

For an integer sequence of length \(n\), \(X=(X_1,\ X_2,\ \dots,\ X_n)\), let \(f(X)\) denote the largest \(s\) satisfying the following.

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

---

[1] Dynamic programming

Let \(dp_i=f((A_1,\ A_2,\ \dots,\ A_i))\) and compute them in the order \(i=1,\ 2,\ \dots\). For convenience, let \(dp_{-1}=-1\) and \(dp_0=0\).

An integer sequence (IS) totaling \(S\) whose last term is \(x\) can be considered as (an IS totaling \(S-x\)) \(+(x)\). Thus, the condition to have every IS totaling \(S\) ending with \(x\) as a subsequence is \(S-x \leq dp_{\mathrm{behind}(i,x)-1}\).

From this, we have \(\displaystyle dp_i=\min_{1\leq x \leq S} (dp_{\mathrm{behind}(i,x)-1}+x)\).

---

[2] Find just the necessary parts

In the above dynamic programming, \(dp_i\) is computed for all \(-1 \le i \le N^2\). However, since \(dp_i\) is monotonic with respect to \(i\), it is enough to find the smallest \(i\) such that \(dp_i=s\) for each \(-1 \leq s \leq S\) (it can be seen that such an \(i\) always exists by considering a sequence of positive integers ending with \(x=1\)). If \(dp_i\) is needed during computation, it can be found with binary search.

Let us think of a way to find the smallest \(i'\) such that \(dp_{i'}=s+1\) when \(dp_{i}=s\ (s < S)\) is known. By considering \(x\) such that \(dp_{\mathrm{behind}(i,x)-1}+x=s\), we see that \(\mathrm{front}(i,x) \leq i'\) is necessary. On the other hand, if this is satisfied, we have \(dp_{\mathrm{behind}(i',x)-1}+x \geq dp_{i}+x \geq s+1\). Thus, the smallest \(i'\) such that \(dp_{i'}=s+1\) is the maximum value of \(\mathrm{front}(i,x)\) for \(x\) such that \(dp_{\mathrm{behind}(i,x)-1}+x=s\).

Therefore, the following algorithm can find \(L\).

1. Initialize with \(L=0\) and \(S_x=x-1\).
2. For \(s=0,\ 1,\ \dots,\ S-1\) in this order, do the following.
   • For \(x\) such that \(S_{x}=s\), let \(L'=\mathrm{front}(L,x)\). For \(i\) such that \(L < i \le L'\), let \(S_{A_i}\leftarrow dp_{\mathrm{behind}(L',A_i)-1}+A_i\) and \(L\leftarrow L'\).

A good point of this algorithm is that the processing in 2. is performed only \(O(\sum_{x=1}^{S}\frac{S}{x})=O(S\log S)\) times since \(S_x\) increases by \(x\) when \(S_x=s\). However, when updating \(L\), one must also update \(S_x=dp_{\mathrm{behind}(L,x)-1}+x\) for each \(x\), which is the bottleneck.

---

[3] Delay the update

So, when updating \(L\), let us not update \(dp_{\mathrm{behind}(L,x)-1}+x\) for each \(x\) to the correct value. Instead, let us update it when \(S_x=s\). That is, use the following algorithm to find \(L\).

1. Initialize with \(L=0,\ T_{x}=x-1\ (1\leq x \le S)\).
2. For \(s=0,\ 1,\ \dots,\ S-1\) in this order, do the following.
   • For \(x\) such that \(T_x=s\), let \(T_x \leftarrow dp_{\mathrm{behind}(L,x)-1}+x\). Then, if \(T_x=s\), let \(L \leftarrow \mathrm{front}(L,x)\) and \(T_x\leftarrow s+x\).

Now, the issue by updating \(T_x\) is resolved, but what about the number of times the processing in 2. is performed?

Actually, after \(T_x=s\) is satisfied twice, \(T_x\) will have increased by at least \(x\).

Proof

\(T_x\) clearly increases by at least \(x\) if \(T_x=s\) after letting \(T_x\leftarrow dp_{\mathrm{behind}(L,x)-1}+x\), so let us consider the case we have \(s < T_x\) twice in a row.

Let \(L_1\) and \(s_1\) be the \(L\) and \(S\) just before the first update, and \(L_2\) and \(s_2\) be those just before the second update. As a result of updating \(T_x\) to the correct value in the second update, we have \(s < T_x\), so it holds that \(s_2=dp_{\mathrm{behind}(L_1,x)-1}+x < dp_{\mathrm{behind}(L_2,x)-1}+x\), and \(L_1 < \mathrm{behind}(L_2,x)\). Thus, we have \(dp_{\mathrm{behind}(L_2,x)-1}+x \geq dp_{L_1}+x=s_1+x\), and \(T_x\) has been incresed by at least \(x\).

Thus, the processing in 2. is again performed \(O(\sum_{x=1}^{S}\frac{S}{x})=O(S\log S)\) times.

Therefore, the above algorithm finds the smallest \(L\) that satisfies the condition in \(O(N+S\log S(\log S + \log N))\) time.