Consider the maximum score that can be achieved with a cost of \(0\).

First, let’s consider the following DP:

\(dp[i][j]=\) when the order of \(P_1, \cdots, P_i\) is determined optimally, the maximum length of an increasing subsequence ending with the \(j\)-th largest value among them.

Note that it is not the \(j\)-th smallest value. This makes the DP transition quite simple.

First, in the case where \(dp[i][j] < dp[i][j+1]\), we can set \(dp[i][j] = dp[i][j+1]\). Also, from the nature of the original problem, we know that \(dp[i][j] - dp[i][j+1] \leq 1\). Therefore, the values of \(dp[i][*]\) can be represented by the set of \(j\) where \(dp[i][j] > dp[i][j+1]\). Let \(S_i\) denote this set. For convenience, we set \(dp[i][i+1] = 0\) and include \(i\) in \(S_i\).

We have \(|S_i| = \max(dp[i]) = \) LIS length. Considering the transition from \(S_i\) to \(S_{i+1}\), we can see the following changes:

• If there is a value in \(S_i\) not greater than \(A_i\), remove the maximum among them.
• Then, add \(i\) to \(S_i\).

By implementing this straightforwardly with a set, we can find the maximum score with a cost of \(0\).

By the way, the operations on \(S_i\) can be transformed as follows:

• Prepare \(S = \{1, 2, \cdots, N\}\).
• For each \(i = 1, 2, \cdots, N\), if there is a value in \(S\) not greater than \(A_i\), remove the maximum among them.

In other words, it is okay to perform the operation of adding values to \(S\) all at once at the beginning. This can be proved by noting that \(A_i < i\). Also, it can be proved that the answer does not change even if the order of the loop for \(i\) is any order other than \(1, 2, \cdots, N\).

Based on this consideration, let’s consider cases where the cost is not \(0\). We assume that paying a cost of \(1\) allows us to choose one \(A_i\) and make it \(0\). Then, it can be seen that we should make \(A_i\) zero in descending order of their values. Now, we can simulate this process using a set or similar structure. We can easily implement it by starting from the cost of \(N\) and considering the operations using \(A_i\) in ascending order of their values.

The time complexity is \(O(N \log N)\).

Sample Solution (C++)