Look at the samples.

Observe that since we are only allowed to choose $$$i \ge 2$$$ to swap $$$a_i$$$ and $$$a_{i+1}$$$, it means that $$$a_1$$$ cannot be modified by the operation. Hence, $$$a_1 = 1$$$ must hold. We can prove that as long as $$$a_1 = 1$$$, we will be able to sort the array.

Consider the largest element of the array. Let its index be $$$i$$$. Our objective is to move $$$a_i$$$ to the end of the array. If $$$i = n$$$, it means that the largest element is already at the end. Otherwise, since $$$a_i$$$ is the largest element, this means that $$$a_{i-1} < a_i$$$ and $$$a_i > a_{i+1}$$$. Hence, we can do an operation on index $$$i$$$ and move the largest element one step closer to the end. We repeatedly do the operation until we finally move the largest element to the end of the array. Then, we can pretend that the largest element does not exist and do the same algorithm for the prefix of size $$$n - 1$$$. Hence, we will able to sort the array by doing this repeatedly.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector <ll> vi;
int main() {
    int t;
    cin >> t;
    while (t --> 0) {
        int n;
        cin >> n;
        vi arr(n);
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        if (arr[0] == 1) {
            cout << "YES";
        } else {
            cout << "NO";
        }
        cout << '\n';
    }
}

What happens when $$$s$$$ starts with some $$$\texttt{B}$$$ and ends with some $$$\texttt{A}$$$?

If the string consists of only $$$\texttt{A}$$$ or only $$$\texttt{B}$$$, no operations can be done and hence the answer is $$$0$$$. Otherwise, let $$$x$$$ be the smallest index where $$$s_x = \texttt{A}$$$ and $$$y$$$ be the largest index where $$$x_y = \texttt{B}$$$. If $$$x > y$$$, this means that the string is of the form $$$s=\texttt{B}\ldots\texttt{BA}\ldots\texttt{A}$$$. Since all the $$$\texttt{B}$$$ are before the $$$\texttt{A}$$$, no operation can be done and hence the answer is also $$$0$$$.

Now, we are left with the case where $$$x < y$$$. Note that $$$s[1,x-1] = \texttt{B}\ldots\texttt{B}$$$ and $$$s[y+1,n] = \texttt{A}\ldots\texttt{A}$$$ by definition. Since the operation moves $$$\texttt{A}$$$ to the right and $$$\texttt{B}$$$ to the left, this means that $$$s[1,x - 1]$$$ will always consist of all $$$\texttt{B}$$$ and $$$s[y + 1, n]$$$ will always consist of all $$$\texttt{A}$$$. Hence, no operation can be done from index $$$1$$$ to $$$x - 1$$$ as well as from index $$$y$$$ to $$$n - 1$$$.

The remaining indices where an operation could be done are from $$$x$$$ to $$$y - 1$$$. It can be proven that all $$$y - x$$$ operations can be done if their order is chosen optimally. Let array $$$b$$$ store the indices of $$$s$$$ between $$$x$$$ and $$$y$$$ that contain $$$\texttt{B}$$$ in increasing order. In other words, $$$x < b_1 < b_2 < \ldots < b_k = y$$$ and $$$b_i = \texttt{B}$$$, where $$$k$$$ is the number of occurences of $$$\texttt{B}$$$ between $$$x$$$ and $$$y$$$. For convenience, we let $$$b_0 = x$$$. Then, we do the operations in the following order:

$$$b_1 - 1, b_1 - 2, \ldots, b_0 + 1, b_0,$$$

$$$b_2 - 1, b_2 - 2, \ldots, b_1 + 1, b_1,$$$

$$$b_3 - 1, b_3 - 2, \ldots, b_2 + 1, b_2,$$$

$$$\vdots$$$

$$$b_k - 1, b_k - 2, \ldots, b_{k - 1} + 1, b_k$$$

It can be seen that the above ordering does operation on all indices between $$$x$$$ and $$$y - 1$$$. To see why all of the operations are valid, we look at each row separately. Each row starts with $$$b_i - 1$$$, which is valid as $$$s_{b_i} = \texttt{B}$$$ and $$$s_{b_i - 1} = \texttt{A}$$$ (assuming that it is not the last operation of the row). Then, the following operations in the same row move $$$\texttt{B}$$$ to the left until position $$$b_{i - 1}$$$. To see why the last operation of the row is valid as well, even though $$$s_{b_{i - 1}}$$$ might be equal to $$$\texttt{B}$$$ initially by definition, either $$$i = 1$$$ which means that $$$s_{b_0} = s_x = \texttt{A}$$$, or an operation was done on index $$$b_{i - 1} - 1$$$ in the previous row which moved $$$\texttt{A}$$$ to index $$$b_{i - 1}$$$. Hence, all operations are valid.

#include <bits/stdc++.h>
using namespace std;
 
char s[200005];
 
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int tc, n; cin >> tc;
	while (tc--) {
		cin >> n; s[n + 1] = 'C';
		for (int i = 1; i <= n; ++i) cin >> s[i];
		int pt1 = 1, pt2 = 1, ans = 0;
		while (s[pt1] == 'B') ++pt1, ++pt2;
		while (pt1 <= n) {
			int cntA = 0, cntB = 0;
			while (s[pt2] == 'A') ++pt2, ++cntA;
			while (s[pt2] == 'B') ++pt2, ++cntB;
			if (s[pt2 - 1] == 'B') ans += pt2 - pt1 - 1;
			if (cntB) pt1 = pt2 - 1;
			else break;
		}
		cout << ans << '\n';
	}
}

Consider a greedy algorithm.

For simplicity, assume that both arrays $$$a$$$ and $$$b$$$ are sorted in increasing order. The final answer can be obtained by permuting the answer array using the same permutation to permute sorted array $$$a$$$ to the original array $$$a$$$.

Claim: If the rearrangement $$$b_{x + 1}, b_{x + 2}, \ldots, b_n, b_1, b_2, \ldots, b_x$$$ does not have beauty $$$x$$$, it is not possible to rearrange $$$b$$$ to make the beauty equals to $$$x$$$.

Proof: Suppose there exists an alternative rearrangement different from above represented by permutation $$$p$$$ where $$$b_{p_1}, b_{p_2}, \ldots, b_{p_n}$$$ results in a beauty of $$$x$$$. Let array $$$q$$$ represent the $$$x$$$ indices where $$$a_i > b_{p_i}$$$ in increasing order. In other words, $$$1 \le q_1 < q_2 < \ldots < q_x \le n$$$ and $$$a_{q_i} > b_{p_{q_i}}$$$. Let $$$i$$$ be the largest index where $$$q_i \neq n - i + 1$$$ ($$$q_i < n - i + 1$$$ also holds due to strict inequality above). We know that $$$a_{q_i} > b_{p_{q_i}}$$$ and $$$a_{n - i + 1} \le b_{p_{n - i + 1}}$$$. Since $$$a$$$ is sorted and $$$q_i < n - i + 1$$$, we have $$$a_{q_i} \le a_{n - i + 1}$$$, and hence, $$$a_{n - i + 1} > b_{p_{q_i}}$$$ and $$$a_{q_i} \le b_{p_{n - i + 1}}$$$. This means that we can swap $$$p_{q_i}$$$ with $$$p_{n - i + 1}$$$ without changing the beauty of the array, while allowing $$$q_i = n - i + 1$$$. Hence, by doing the swapping repeatedly, we will get $$$q_i = n - i + 1$$$ for all $$$i$$$ between 1 and $$$x$$$.

An alternative interpretation to the result above is that we managed to obtain a solution where for all $$$i$$$ between $$$1$$$ and $$$n - x$$$, we have $$$a_i \le b_{p_i}$$$. On the other hand, for all $$$i$$$ between $$$n - x + 1$$$ and $$$n$$$, we have $$$a_i > b_{p_i}$$$. Let $$$i$$$ be the largest index between $$$1$$$ and $$$n - x$$$ where $$$p_i \neq i + x$$$ ($$$p_i < i + x$$$ due to maximality). Then, let $$$j$$$ be the index where $$$p_j = i + x$$$. Consider two cases:

• $$$j \le n - x$$$. Since $$$i$$$ is the largest index where $$$p_i \neq i + x$$$, this means that $$$j < i$$$ and hence $$$a_j \le a_i$$$. We have $$$a_i \le b_{p_i} \le b_{i + x} = b_{p_j}$$$ and $$$a_j \le a_i \le b_{p_i}$$$. Hence, we can swap $$$p_i$$$ and $$$p_j$$$ without changing the beauty of the array, while allowing $$$p_i = i + x$$$.
• $$$j > n - x$$$. We have $$$a_i \le b_{p_i} \le b_{i + x} = b_{p_j}$$$ and $$$a_j > b_{p_j} = b_{i + x} > b_{p_i}$$$. Hence, we can swap $$$p_i$$$ and $$$p_j$$$ without changing the beauty of the array, while allowing $$$p_i = i + x$$$.

By repeating the above repeatedly, we can obtain a solution where $$$p_i = i + x$$$ for all $$$i$$$ between $$$1$$$ and $$$n - x$$$. Let $$$i$$$ be the smallest index between $$$n - x + 1$$$ and $$$n$$$ where $$$p_i \neq i - n + x$$$ ($$$p_i > i - n + x$$$ by minimality). Then, let $$$j$$$ be the index where $$$p_j = i - n + x$$$. Note that $$$j > n - x$$$ as well since $$$p_i = i + x$$$ for all $$$i$$$ between $$$1$$$ and $$$n - x$$$. Since $$$i$$$ is the smallest index where $$$p_i \neq i - n + x$$$, this means that $$$i < j$$$ and hence $$$a_i \le a_j$$$. We have $$$a_i > b_{p_i} \ge b_{i - n + x} = b_{p_j}$$$ and $$$a_j \ge a_i > b_{p_i}$$$. Hence, we can swap $$$p_i$$$ and $$$p_j$$$ without changing the beauty of the array, while allowing $$$p_i = i - n + x$$$. By doing this repeatedly, we can obtain a solution where $$$p_i = i - n + x$$$ for all $$$i$$$ between $$$n - x + 1$$$ and $$$n$$$. Now, $$$p = [x + 1, x + 1, \ldots, n, 1, 2, \ldots, x]$$$, which matches the rearrangement in our claim.

#include <bits/stdc++.h> 
using namespace std;
 
#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
 
const int INF = 1000000005;
const int MAXN = 200005;
 
int t;
int n, x;
int a[MAXN], b[MAXN], aid[MAXN];
int ans[MAXN];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> t;
    while (t--) {
        cin >> n >> x;
        REP (i, 0, n) {
            cin >> a[i];
        }
        REP (i, 0, n) {
            cin >> b[i];
        }
        iota(aid, aid + n, 0);
        sort(aid, aid + n, [&] (int l, int r) {
                return a[l] < a[r];
                });
        sort(b, b + n);
        REP (i, 0, x) {
            ans[aid[n - x + i]] = b[i];
        }
        REP (i, x, n) {
            ans[aid[i - x]] = b[i];
        }
        REP (i, 0, n) {
            x -= a[i] > ans[i];
        }
        if (x == 0) {
            cout << "YES\n";
            REP (i, 0, n) {
                cout << ans[i] << ' ';
            }
            cout << '\n';
        } else {
            cout << "NO\n";
        }
    }
    return 0;
}

Consider some small examples and write down every possible value of subarray sums. Can you see some patterns?

Denote $$$s[l,r]$$$ as the sum of subarray from $$$l$$$ to $$$r$$$.

Claim: If there is any subarray with sum $$$v\ge 2$$$, we can find a subarray with sum $$$v-2$$$.

Proof: Suppose $$$s[l,r]=v$$$, consider 3 cases:

• $$$a[l]=2$$$, we have $$$s[l+1,r]=v-2$$$.
• $$$a[r]=2$$$, we have $$$s[l,r-1]=v-2$$$.
• $$$a[l]=a[r]=1$$$, we have $$$s[l+1,r-1]=v-2$$$.

So to check if there exists a subarray whose sum equals $$$v$$$, we can find the maximum subarray sum having the same parity with $$$v$$$ and compare it with $$$v$$$.

The case where $$$(s[1,n]-v)\%2=0$$$ is obvious, suppose the opposite happens. If array $$$a$$$ is full of $$$2$$$-s, the answer is $$$\texttt{NO}$$$. Otherwise, let $$$x$$$ and $$$y$$$ be the positions of the first $$$1$$$ and last $$$1$$$ in $$$a$$$. Any subarray with $$$l\le x\le y\le r$$$ will have a different parity with $$$v$$$. So we will compare $$$\max(s[x+1, n],s[1,y-1])$$$ with $$$v$$$ to get the answer.

#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t; cin >> t;
    while (t--) {
        int n, q; cin >> n >> q;
        vector<int> a(n);
        set<int> pos;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            if (a[i] == 1) pos.insert(i);
        }
        while (q--) {
            int cmd; cin >> cmd;
            if (cmd == 1) {
                int v; cin >> v;
                int num = pos.size();
                if ((v - num) & 1) {
                    if (num == 0) cout << "NO";
                    else {
                        int s1 = 2 * *pos.rbegin() - (num - 1);
                        int s2 = 2 * (n - *pos.begin() - 1) - (num - 1);
                        if (v <= max(s1, s2)) cout << "YES";
                        else cout << "NO";
                    }
                } else {
                    if (v <= 2 * n - num) cout << "YES";
                    else cout << "NO";
                }
                cout << '\n';
            } else {
                int i; cin >> i; i--;
                pos.erase(i);
                cin >> a[i];
                if (a[i] == 1) pos.insert(i);
            }
        }
    }
}

For each index $$$i$$$ from $$$1$$$ to $$$n$$$, let $$$h_i$$$ denote the number of cyclic shifts needed to move $$$a_i$$$ to its correct spot. In other words, $$$h_i$$$ is the minimum value such that $$$(i + h_i - 1)\ \%\ n + 1 = a_i$$$. How can we get the answer from $$$h_i$$$?

For convenience, we will assume that the array is cyclic, so $$$a_j = a_{(j - 1)\ \%\ n + 1}$$$. The answer for each index $$$i$$$ from $$$1$$$ to $$$n$$$ is $$$h_i$$$ (defined in hint 1) minus the number of indices $$$j$$$ where $$$i < j < i + h_i$$$ and $$$i < a_j < i + h_i$$$ (or $$$i < a_j + n < i + h_i$$$ to handle cyclic case when $$$i + h_i > n$$$). This is because the value that we are calculating is equal to the number of positions that $$$a_i$$$ will skip during the rotation as the index is already good.

To calculate the above value, it is convenient to define an array $$$b$$$ of size $$$2n$$$ where $$$b_i = a_i$$$ for all $$$i$$$ between $$$1$$$ to $$$n$$$, and $$$b_i = a_{i - n} + n$$$ for all $$$i$$$ between $$$n + 1$$$ to $$$2n$$$ to handle cyclicity. We will loop from $$$i = 2n$$$ to $$$i = 1$$$, and do a point increment to position $$$a_i$$$ if $$$a_i \ge i$$$, otherwise, do a point increment to position $$$a_i + n$$$. Then, to get the answer for index $$$i$$$, we do a range sum query from $$$i + 1$$$ to $$$i + h_i - 1$$$. Point increment and range sum query can be done using a binary indexed tree in $$$O(\log n)$$$ time per query/update. Hence, the problem can be solved in $$$O(n\log n)$$$ time.

#include <bits/stdc++.h> 
using namespace std;
 
#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
 
const int INF = 1000000005;
const int MAXN = 1000005;
 
int t;
int n;
int p[MAXN];
int ans[MAXN];
 
int fw[MAXN * 2];
void incre(int i, int x) {
    for (; i <= 2 * n; i += i & -i) {
        fw[i] += x;
    }
}
int qsm(int i) {
    int res = 0;
    for (; i > 0; i -= i & -i) {
        res += fw[i];
    }
    return res;
}
inline int qsm(int s, int e) {
    return qsm(e) - qsm(s - 1);
}
 
int main() {
#ifndef DEBUG
    ios::sync_with_stdio(0), cin.tie(0);
#endif
    cin >> t;
    while (t--) {
        cin >> n;
        REP (i, 1, n + 1) {
            cin >> p[i];
        }
        REP (i, 0, 2 * n + 5) {
            fw[i] = 0;
        }
        vector<pair<int, int>> rgs;
        REP (i, 1, n + 1) {
            if (i <= p[i]) {
                rgs.push_back({i, p[i]});
                rgs.push_back({i + n, p[i] + n});
            } else {
                rgs.push_back({i, p[i] + n});
            }
        }
        sort(ALL(rgs), greater<pair<int, int>>());
        for (auto [l, r] : rgs) {
            if (l <= n) {
                ans[p[l]] = r - l - qsm(l, r);
            }
            incre(r, 1);
        }
        REP (i, 1, n + 1) {
            cout << ans[i] << ' ';
        }
        cout << '\n';
    }
    return 0;
}

The operation is equivalent to toggling $$$s$$$ at every odd $$$i$$$ where $$$b_i$$$ is an open bracket and every even $$$i$$$ where $$$b_i$$$ is a closed bracket.

Every operation will always toggle $$$s_1$$$ and $$$s_n$$$. Furthermore, every operation will always toggle an even number of positions.

If $$$s_1 \neq s_n$$$ or there is an odd number of $$$\texttt{1}$$$s in $$$s$$$, it is not possible to change all elements of $$$s$$$ to $$$\texttt{0}$$$. Otherwise, it is always possible.

If it is possible to change all elements of $$$s$$$ to $$$\texttt{0}$$$, at most $$$3$$$ operations are needed.

From hint 3, we know the cases where it is impossible to change all elements of $$$s$$$ to $$$\texttt{0}$$$. We will now only consider the case where it is possible to change all elements of $$$s$$$ to $$$\texttt{0}$$$.

Using hint 1, we can easily check whether it is possible to change all elements of $$$s$$$ to $$$\texttt{0}$$$ using only one operation by first constructing the bracket sequence and then checking whether the resultant bracket sequence is balanced. From now on, we will assume that it is not possible to change all elements of $$$s$$$ to $$$\texttt{0}$$$ using one operation.

Suppose $$$s_1 = s_n = \texttt{1}$$$. We know from hint 2 that each operation will always toggle $$$s_1$$$ and $$$s_n$$$, so since it is not possible to change all elements of $$$s$$$ to $$$\texttt{0}$$$ using one operation, we will need three operations. If we let the first operation be $$$b=\texttt{(()()}\ldots\texttt{()())}$$$, $$$s_1$$$ and $$$s_n$$$ will be toggled while the remaining elements stay the same. Now, $$$s_1 = s_n = \texttt{0}$$$, so if we can solve this case using only two operations, it means that we can solve the $$$s_1 = s_n = \texttt{1}$$$ case using only three operations.

To solve the final case where $$$s_1 = s_n = \texttt{0}$$$, we will look at a special balanced bracket sequences $$$b = \texttt{(()()}\ldots\texttt{()())}$$$. Notice that if we do an operation using this bracket sequence, only $$$s_1$$$ and $$$s_n$$$ will be toggled. Suppose there exist an index $$$i$$$ between $$$2$$$ and $$$2n - 2$$$ where we want to toggle both $$$s_i$$$ and $$$s_{i + 1}$$$. We can take the special balanced bracket sequence $$$b = \texttt{(()()}\ldots\texttt{()())}$$$, then swap $$$b_i$$$ and $$$b_{i + 1}$$$. This will always result in a balanced bracket sequence that will toggle $$$s_1$$$, $$$s_n$$$, as well as the desired $$$s_i$$$ and $$$s_{i + 1}$$$. This will allow us to change all elements of $$$s$$$ to $$$\texttt{0}$$$ in $$$2n$$$ moves as we can scan from $$$i = 2$$$ to $$$i = 2n - 2$$$ and do an operation toggling $$$s_i$$$ and $$$s_{i+1}$$$ if $$$s_i = \texttt{1}$$$. Since there is an even number of $$$\texttt{1}$$$s in $$$s$$$ from hint 3, toggling adjacent positions will always change all elements of $$$s$$$ to $$$\texttt{0}$$$.

To reduce the number of operations from $$$2n$$$ to $$$2$$$, notice that a lot of the operations can be parallelized into a single operation. Let $$$A_0$$$ represent the set of even indices between $$$2$$$ and $$$2n - 2$$$ where we want to toggle $$$s_i$$$ and $$$s_{i + 1}$$$. Similarly, let $$$A_1$$$ represent the set of odd indices between $$$2$$$ and $$$2n - 2$$$ where we want to toggle $$$s_i$$$ and $$$s_{i + 1}$$$. In a single operation, we can take the special balanced bracket sequence $$$b = \texttt{(()()}\ldots\texttt{()())}$$$, and swap $$$b_i$$$ and $$$b_{i + 1}$$$ for all $$$i$$$ that is in the set $$$A_0$$$. Since $$$A_0$$$ only contains even indices, the swaps are non-intersecting, and hence, the resultant bracket sequence will still be balanced and $$$s_1$$$, $$$s_n$$$, as well as $$$s_i$$$ and $$$s_{i + 1}$$$ will be toggled for all the desired even indices $$$i$$$. We can use the same strategy with $$$A_1$$$, starting with the same special balanced bracket sequence and then swapping $$$b_i$$$ and $$$b_{i + 1}$$$ for all $$$i$$$ that is in set $$$A_1$$$. Hence, after using these two operations, all elements of $$$s$$$ will change to $$$\texttt{0}$$$.

We will demonstrate a way to use $$$2$$$ bracket sequence to solve any binary string whose first and last element is $$$\texttt{0}$$$ and who also has an even number of $\texttt{1}$s.

Defined the balance of an (incomplete) bracket sequence as the number of open brackets minus the number of closed brakcets. For example, ((() has balance $$$2$$$, (()()(( has balance $$$3$$$ and () has balance $$$0$$$.

Using hint $$$1$$$ we can see that the resulting binary string will contain 0 at position $$$i$$$ iff the character at position $$$i$$$ in both bracket sequences is the same. Suppose the balance of your current bracket sequences is $$$(a,b)$$$. You can change it $$$(a\pm 1, b\pm 1)$$$. If both $$$\pm$$$ have the same parity, then the resulting binary string will contain $$$\texttt{0}$$$ at that position.

Now, we will demonstrate a greedy algorithm.

$$$(0,0) \to (1,1) \to (0,2),(2,2) \to (1,3),(1,1) \to (0,2),(2,2) \to \ldots \to (1,1) \to (0,0)$$$

One can show by a simple parity argument that the second last balance must necessarily be $$$(1,1)$$$ since the number of $\texttt{1}$s in the string is even.

Similar to solution 2, we will demonstrate a way to use $$$2$$$ bracket sequence to solve any binary string whose first and last element is $$$\texttt{0}$$$ and who also has an even number of $\texttt{1}$s.

Using the same greedy argument in solution 2 (or by guessing), we know that we can always use two bracket sequences where the number of open brackets minus the number of close brackets is always between $$$0$$$ and $$$3$$$ for all prefixes of the bracket sequence. For convenience, we will define "balance" as the number of open brackets minus the number of close brackets.

Hence, we can do dynamic programming using the states $$$dp[i][balance1][balance2]$$$ which returns whether it is possible to create two bracket sequences $$$b1$$$ and $$$b2$$$ of length $$$i$$$ such that the balance of $$$b1$$$ and $$$b2$$$ are $$$balance1$$$ and $$$balance2$$$ respectively and $$$s[1, i]$$$ becomes all $$$\mathtt{0}$$$. The transition can be done by making sure that the balances stay between $$$0$$$ and $$$3$$$ and that $$$b1_i \neq b2_i$$$ if $$$s_i=\mathtt{1}$$$ and vice versa.

#include <bits/stdc++.h>
using namespace std;

void solve(int n, string s) {
	vector<int> a;
	for (char &i : s) {
		a.push_back(i & 1);
	}
	
	if (a.front() != a.back()) {
		cout << -1 << endl;
		return ;
	}
	
	if (count(a.begin(), a.end(), 1) % 2) {
		cout << -1 << endl;
		return ;
	}
	
	bool flipped = false;
	if (a.front() == 1 && a.back() == 1) {
		for (int &i : a) i ^= 1;
		flipped = true;
	}
	
	string l(2 * n, '-'), r(2 * n, '-');
	int cnt = 0;
	for (int i = 0; i < 2 * n; i++) {
		if (a[i]) {
			l[i] = (cnt) ? '(' : ')';
			r[i] = (cnt ^ 1) ? '(' : ')';
			cnt ^= 1;
		}
	}
	
	int tot = count(a.begin(), a.end(), 0) / 2;
	cnt = 0;
	for (int i = 0; i < 2 * n; i++) {
		if (!a[i]) {
			if (cnt < tot) l[i] = '(', r[i] = '(';
			else l[i] = ')', r[i] = ')';
			cnt++;
		}
	}
	
	if (flipped) {
		cout << 3 << endl;
		cout << l << endl;
		cout << r << endl;
		for (int i = 0; i < n; i++) cout << "()";
		cout << endl;
	} else {
		cout << 2 << endl;
		cout << l << endl;
		cout << r << endl;
	}
}

int main() {	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		string s;
		cin >> s;
		solve(n, s);
	}
	
	return 0;
}

Find the fastest pepe in $$$n + 1$$$ queries.

After knowing the fastest pepe, find the second fastest pepe in $$$n + 1$$$ queries.

Note that the above process for Hint 2 uses a lot of repeated queries. Can we optimize it to $$$2$$$ queries?

Solve the problem using $$$2n^2 - n + 1$$$ queries.

Call a pepe slow if it does not belong in the fastest $$$n^2 - n + 1$$$ pepes. Note that there are $$$n - 1$$$ slow pepes, and we do not care for their relative speed. After each query, we know that the fastest pepe cannot be slow.

We use the algorithm in hint 4 until there are $$$2n - 1$$$ pepes left. Since the head of $$$n$$$ groups cannot be slow, we are left with exactly $$$(2n - 1) - n = n - 1$$$ candidates for slow pepes. Once we determine the $$$n - 1$$$ slow pepes, we only need to find the ranking of the other $$$n$$$ pepes, which can be done using $$$n - 1$$$ queries.

Total number of queries is $$$n + 2(n^2 - 2n + 1) + (n - 1) = 2n^2 - 2n + 1$$$.

We will try to decrease the number of queries based on the fact that we can omit one query for recalculation when the size of a group decreases from $$$2$$$ to $$$1$$$.

We modify the algorithm in hint 4 to maintain an invariant: $$$|G_i| - |G_j| \le 1$$$ $$$\forall \, 1 \le i < j \le n$$$. In other words, we want to make the sizes of these groups as balanced as possible.

To maintain this, whenever we have $$$|G_j| - |G_i| = 2$$$ after removing some pepe, we can transfer any non-head pepe from $$$G_j$$$ to $$$G_i$$$ to balance these groups out. Next, to recalculate the head of $$$G_i$$$, we will "borrow" instead of "steal" from other groups. If the fastest pepe is borrowed from $$$G_j$$$, then we transfer a random non-head pepe in $$$G_i$$$ back to $$$G_j$$$. This works since the head of $$$G_j$$$ is faster than the head of $$$G_i$$$, which in turn is faster than the random pepe.

Finally, when there are $$$2n$$$ pepes left, all groups have the size of $$$2$$$, and we only need to use $$$1$$$ query for each pepe from later on.

Total number of queries is $$$n + 2(n^2 - 2n) + (n + 1) = 2n^2 - 2n + 1$$$.

#include <bits/stdc++.h>

using namespace std;

const int N = 30;

vector<int> buc[N];
int buc_id[N * N], buc_max[N];
int n;

int ask(vector<int> que) {
  cout << "?";
  for (int i : que) cout << ' ' << i + 1;
  cout << endl;
  int res; cin >> res;
  return res - 1;
}

int ask_all() {
  vector<int> que;
  for (int i = 0; i < n; i++)
    if (buc[i].size())
      que.push_back(buc_max[i]);
  for (int i = 0; i < n; i++)
    for (int j : buc[i])
      if (int(que.size()) < n && j != buc_max[i])
        que.push_back(j);
  return ask(que);
}

void answer(vector<int> ans) {
  cout << "!";
  for (int i : ans) cout << ' ' << i + 1;
  cout << endl;
}

void add(int id, int pepe) {
  buc[id].push_back(pepe);
  buc_id[pepe] = id;
}

void remove(int id, int pepe) {
  buc[id].erase(find(buc[id].begin(), buc[id].end(), pepe));
}

void send(int id, vector<int> &que) {
  for (int pepe : buc[id])
    if (int(que.size()) < n && pepe != buc_max[id])
      que.push_back(pepe);
}

void check_balance() {
  size_t min_size = n, max_size = 0;
  for (int id = 0; id < n; id++) {
    min_size = min(min_size, buc[id].size());
    max_size = max(max_size, buc[id].size());
  }
  assert(max_size - min_size <= 1);
}


int main() {
  cout << endl;
  int t; cin >> t;
  while (t--) {
    cin >> n;
    for (int id = 0; id < n; id++)
      buc[id].clear();
      
    for (int pepe = 0; pepe < n * n; pepe++) {
      buc_id[pepe] = pepe / n;
      buc[pepe / n].push_back(pepe);
    }
    
    for (int id = 0; id < n; id++)
      buc_max[id] = ask(buc[id]);
      
    vector<int> ans;
    
    /// balancing phase
    for (int step = 0; step < n * n - 2 * n; step++) {
      ans.push_back(ask_all());
      int last_id = buc_id[ans.back()];
      remove(last_id, ans.back());
      
      vector<int> que;
              
      for (int pepe : buc[last_id])
        que.push_back(pepe);
        
      /// find bucket with largest size != last_id
      int max_id = (last_id == 0);
      for (int id = 0; id < n; id++)
        if (id != last_id && buc[id].size() > buc[max_id].size())
          max_id = id;
          
      
      send(max_id, que);
      
      for (int id = 0; id < n; id++)
        if (id != max_id && id != last_id)
          send(id, que);
      
      buc_max[last_id] = ask(que);
      int move_id = buc_id[buc_max[last_id]];
      if (move_id != last_id) {
        remove(move_id, buc_max[last_id]);
        add(move_id, buc[last_id].back());
        remove(last_id, buc[last_id].back());
        add(last_id, buc_max[last_id]);
      }        
      
      if (buc[last_id].size() == buc[max_id].size() - 2) {
        if (move_id == max_id) {
          add(last_id, buc[move_id].back());
          remove(move_id, buc[move_id].back());
        } else {
          for (int pepe : buc[max_id])
            if (pepe != buc_max[max_id]) {
              add(last_id, pepe);
              remove(max_id, pepe);
              break;
            }
        }
      }
      
      check_balance();
    }
  
    
    for (int step = 0; step < n + 1; step++) {
      ans.push_back(ask_all());
      int last_id = buc_id[ans.back()];
      remove(last_id, ans.back());
      if (buc[last_id].size())
        buc_max[last_id] = buc[last_id][0];
    }
    
    answer(ans);
  }
}

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define debug(x) cout << #x << ": " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n;
vector<int> v[25];

int ask(vector<int> v){
	cout<<"? "; for (auto it:v) cout<<it<<" "; cout<<endl;
	int res; cin>>res;
	return res;
}

vector<int> fix(vector<int> v){
	int t=ask(v);
	rep(x,0,n) if (v[x]==t) swap(v[0],v[x]);
	return v;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	int TC;
	cin>>TC;
	while (TC--){
		cin>>n;
		rep(x,0,n){
			v[x].clear();
			rep(y,1,n+1) v[x].pub(x*n+y);
		}
		
		rep(x,0,n) v[x]=fix(v[x]);
		
		vector<int> ans;
		rep(x,0,n*n-2*n+1){
			vector<int> t;
			rep(x,0,n) t.pub(v[x][0]);
			int best=ask(t);
			
			int idx=-1;
			rep(x,0,n) if (t[x]==best) idx=x;
			
			ans.pub(best);
			v[idx].erase(v[idx].begin());
			
			rep(x,0,n) if (x!=idx){
				while (sz(v[x])>1 && sz(v[idx])<n){
					v[idx].pub(v[x].back());
					v[x].pob();
				}
			}
			v[idx]=fix(v[idx]);
		}
		
		vector<int> a,b;
		rep(x,0,n){
			rep(y,0,sz(v[x])){
				if (y==0) a.pub(v[x][y]);
				else b.pub(v[x][y]);
			}
		}
		set<int> bad=set<int>(all(b));
		
		rep(x,0,n-1){
			a=fix(a);
			ans.pub(a[0]);
			a.erase(a.begin());
			a.pub(b.back()); b.pob();
		}
		
		for (auto it:a) if (!bad.count(it)) ans.pub(it);
		
		cout<<"! "; for (auto it:ans) cout<<it<<" "; cout<<endl;
	}
	
}

For any $$$c$$$ which is a cyclic shift of $$$t$$$, what will happen if $$$h(s,c)>2^k$$$?

Try finding some useful relationship between $$$1$$$-s of $$$s$$$ and $$$1$$$-s of $$$c$$$.

Think about polynomial multiplication.

Sort $$$0,1,\ldots,2n-1$$$ based on their bit-reversal values and build a binary tree on top of it. What condition should be satisfied on each level of the tree?

Consider the polynomial product $$$A=S\cdot T$$$, where $$$S=\sum s[i]x^i$$$ and $$$T=\sum t[2n-i-1]x^i$$$ (reversed coefficients).

Claim 1. For all $$$0\le i<2n$$$, we have $$$A[x^i]+A[x^{i+2n}]=n/2$$$, where $$$A[x^k]$$$ denote the coefficient of $$$x^k$$$ in $$$A$$$.

Claim 2. We can express $$$A=(x+1)(x^2+1)(x^4+1)\ldots (x^n+1)(n/2+C(x-1))$$$ where $$$C$$$ is some polynomial with degree not greater than $$$2n-2$$$.

It is easy to see that this result satisfies claim 1.

Claim 3. Since $$$x^{2^p}+1$$$ is cyclotomic polynomial and hence irreducible for all $$$p$$$, each factor in $$$x+1,x^2+1,\ldots,x^n+1$$$ must divide at least one of $$$S$$$ and $$$T$$$. And under the constraints that each of $$$s$$$ and $$$t$$$ must have exactly $$$n$$$ $$$1$$$-s, this condition is also sufficient.

Recall $$$n=2^k$$$, define $$$f_s(mask)$$$ ($$$0\le mask<2n$$$) as the number of string $$$s$$$ such that for each $$$p$$$ where $$$p$$$-th bit of $$$mask$$$ is on, $$$S$$$ is divisible by $$$x^{p}+1$$$. Define $$$f_t$$$ similarly for $$$T$$$. Define $$$f^{\prime}_t$$$ such that $$$f^{\prime}_t(mask)=f_t(mask\odot (2n-1))$$$ where $$$\odot$$$ denotes bitwise XOR.

The answer to the problem is $$$\displaystyle\sum_{mask} f_s(mask)\cdot \mu(f^{\prime}_t(mask))$$$ where $$$\mu$$$ denote Mobius transform. The reason we need Mobius transform is that $$$mask_s$$$ does not represent all divisors, just a subset of it.

Let rearrange elements of $$$s$$$ into a new array $$$s^{\prime}$$$ so that $$$s^{\prime}[\text{reverse_bit}(i)]=s[i]$$$ (for example, with $$$n=8$$$, the new order will be $$$[0,8,4,12,2,6,10,14,1,9,5,13,3,11,7,15]$$$). Construct a perfect binary tree based on the array $$$s^{\prime}$$$. This binary will have $$$k+2$$$ levels from $$$0$$$ to $$$k+1$$$, starting at the root.

Claim 4. $$$S$$$ is divisible by $$$x^{2^p}+1$$$ if only if for every tree node at $$$p$$$-th level, the number of $$$1$$$-s of $$$s^{\prime}$$$ under both children are equal (the proof is left as an exercise for readers).

Consider the following dynamic programming: $$$dp_s[i][mask][num]$$$, where the levels in $$$mask$$$ satisfy claim 4 and $$$num$$$ is the number of $$$1$$$-s under $$$i$$$-th node on the tree. Denote $$$l$$$ as level of $$$i$$$-th node, transitions are:

• $$$dp_s[i][mask][num_1+num_2]\text{ += }dp_s[2i][mask][num_1]\cdot dp_s[2i+1][mask][num_2]$$$
• $$$dp_s[i][mask+2^l][2\cdot num]\text{ += }dp_s[2i][mask][num]\cdot dp_s[2i+1][mask][num]$$$

The above dp took $$$\mathcal{O}(n^3)$$$, which is sufficient to solve the easy version.

To solve the hard version, we will optimize the above transitions:

• The first transition is actually the convolution of $$$dp_s[2i][mask]$$$ and $$$dp_s[2i+1][mask]$$$, we can use FFT to optimize it.
• In the second transition, because $$$num$$$ is multiplied by $$$2$$$ every time, we can omit it and just make the transition to $$$dp_s[i][mask+2^l][num]$$$, reduce the length of $$$dp_s[i][mask+2^l]$$$ by two.

By careful analysis, we can show that the time complexity is now $$$\mathcal{O}(3^k\cdot k)$$$ (recall $$$n=2^k$$$) with a fair constant factor, which solved the hard version.