Observation: We will add cow $c$ to the back of line $b$ if and only if $a_c = \max(a_c, a_{c+1}, \ldots, a_N)$.
Proof: Suppose we have already considered cows $a_1, a_2, \ldots, a_{c-1}$ and temporarily constructed an array $b_1, b_2 \ldots b_{k-1}$. Let's say $a_c = \max(a_c, a_{c+1}, \ldots, a_N)$ and we want to consider if adding it to the back of $b$ is optimal. It's important to note that:
Therefore, it is optimal add $a_c$ as $b_k$ if and only if $a_c = \max(a_c,\ldots, a_N)$.
Subtask $1$: $N \leq 100$
It suffices to fix the position of the old and new positions of the cow we will remove to the front, and recompute $b$ every time. This runs in $\mathcal{O}(N^3)$.
Full Credit
Let's consider the preliminary array $b$, constructed before the operation is performed. Let's denote another array $p_i$ that represents the position where $b_i$ is taken from $a$.
Consider an index $j$ such that $b_j > b_{j+1}$. Note that it is pointless to move $b_{j+1}$ before $p_j$, since $b_{j+1}$ will no longer be a suffix maximum of $a$. Therefore, the only way we can improve $b$ is through inserting new elements after $p_{j+1}$, and these new elements must be new suffix maximums that appear after we move $b_{j+1}$ forwards.
To maximize the number of candidate suffix maximums, it is optimal to move $b_{j+1}$ right before index $p_j+1$. Why? Consider element $a_k$ where $p_j < k < p_{j+1}$, $a_k < b_j$ and there is no other element after index $p_{j+1}$ that is greater than $a_k$. After moving $b_{j+1}$ to a position before $k$, $a_k$ will become a suffix maximum if there is no position $l \in [k+1, p_{j+1}-1]$ where $a_l > a_k$. To maximize the number of candidates for $a_k$, we want the number of elements between $p_{j+1}$ after the move and $p_{j+2}$ to be as large as possible. Any element between those two indices can potentially be a new suffix maximum.
What other elements can we insert in $b$ after the move? Consider a non-increasing subsequence $s_1, s_2, \ldots, s_m$ formed by elements indexed within $[p_j+1, p_{j+2}-1$], excluding $p_{j+1}$. If $s_1 < b_{j+1}$ and $s_m \geq b_{j+2}$, then all of those elements can be inserted behind $b_{j+1}$, as they will all become suffix maximums, since $b_j$ is moved before $p_j+1$.
Note that we will also need to consider $j$ where $b_j = b_{j+1}$. Even if we move $b_{j+1}$ before $p_j$, it is still a suffix maximum. However, this move will not improve the number of candidate suffix maximums, as it the upper bound for the suffix maximums will be $b_j$, which is equivalent to $b_{j+1}$.
It is pointless to consider moving cows not in $b$, since more suffix maximums can't be produced. Additionally, since you may want to move an element before the start of the array, it may be useful to denote $b_0 = \infty$.
Finally, to obtain the lexicographically greatest result, it is optimal to consider the first index $j$ such that a non-empty subsequence of suffix maximums can be newly inserted behind $b_{j+1}$.
#include <bits/stdc++.h> using namespace std; int main(){ int T; cin >> T; while(T--){ int N; cin >> N; vector<int> a(N); for(int i = 0; i < N; i++) cin >> a[i]; // build array b without the operation // the second element in the pair is the index taken from a vector<pair<int, int>> b; int suff_max = -1; for(int i = N - 1; i >= 0; i--){ suff_max = max(suff_max, a[i]); if(suff_max == a[i]) b.push_back({a[i], i}); } reverse(b.begin(), b.end()); b.insert(b.begin(), {N + 1, -1}); // append arbitrary large number to start of b b.push_back({-1, N}); // append arbitrary small number to end of b for(int i = 1; i < (int) b.size() - 1; i++){ vector<pair<int, int>> add; suff_max = b[i+1].first; for(int j = b[i+1].second - 1; j > b[i-1].second; j--){ if(b[i].second == j) continue; suff_max = max(suff_max, a[j]); if(suff_max == a[j]) add.push_back({a[j], j}); } reverse(add.begin(), add.end()); if(!add.empty()){ b.insert(b.begin() + i + 1, add.begin(), add.end()); break; } } for(int i = 1; i < (int) b.size() - 1; i++){ cout << b[i].first << " \n"[i + 2 == (int) b.size()]; } } } // Bessie says hi vvv /* \|/ (__) `\------(oo) || (__) ||w--|| \|/ \|/ */