Let us determine what is required for every position to contain exactly one element after the simultaneous move.

The element initially at position $$$1$$$ cannot move to the left, so it must move to the right. Therefore, $$$w_1 \gt k$$$. Once it leaves, only the element initially at position $$$2$$$ can fill position $$$1$$$, so $$$w_2 \lt k$$$.

Thus, the elements at positions $$$1$$$ and $$$2$$$ must swap. Repeating the same argument for the remaining positions, the only possible movement pattern is

Consequently, $$$n$$$ must be even, every element at an odd position must move to the right, and every element at an even position must move to the left.

Let

We need an integer $$$k$$$ such that $$$L \lt k \lt R$$$. Such an integer exists if and only if $$$L+2\le R$$$.

The time complexity is $$$O(n)$$$ per test case, and the extra space complexity is $$$O(1)$$$.

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

void work() {
	int n; cin >> n;
	long long L = 0, R = 1000000001LL;

	for (int i = 1; i <= n; ++i) {
		long long w; cin >> w;
		if (i & 1) R = min(R, w);
		else L = max(L, w);
	}

	cout << (n % 2 == 0 && L + 2 <= R ? "YES" : "NO") << '\n';
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int T; cin >> T;
	while (T--) work();

	return 0;
}

Partition the string into maximal blocks of equal characters. How does the number of blocks determine the number of adjacent equal pairs?

Define a block as a maximal consecutive segment of equal characters. Suppose the string has $$$r$$$ blocks with lengths $$$l_1,l_2,\ldots,l_r$$$. A block of length $$$l_i$$$ contributes exactly $$$l_i-1$$$ adjacent equal pairs, so the total number is

Therefore, we need to construct a string with exactly $$$r=n-k$$$ blocks.

Because $$$k \lt n$$$, we have $$$r\ge1$$$. Since $$$n\ge2$$$ and the counts of $$$\mathtt{0}$$$ and $$$\mathtt{1}$$$ may differ by at most $$$1$$$, both characters must appear, so the string must contain at least two blocks. Hence, when $$$r=1$$$, or equivalently $$$k=n-1$$$, no solution exists.

Now assume $$$r\ge2$$$. Let the block characters alternate, starting with $$$\mathtt{0}$$$. The numbers of $$$\mathtt{0}$$$-blocks and $$$\mathtt{1}$$$-blocks are

We want the total numbers of the two characters to be

First assign one character to each block. This uses $$$r_0$$$ zeros and $$$r_1$$$ ones. Since $$$r\le n$$$, we have $$$r_0\le c_0$$$ and $$$r_1\le c_1$$$.

Append all remaining zeros to any $$$\mathtt{0}$$$-block and all remaining ones to any $$$\mathtt{1}$$$-block, then concatenate the blocks in order. The two character counts differ by at most $$$1$$$, and the string has exactly $$$r$$$ blocks, so it contains exactly $$$n-r=k$$$ adjacent equal pairs.

The time complexity is $$$O(n)$$$ per test case and $$$O(\sum n)$$$ in total. The space complexity is $$$O(n)$$$.

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

void work() {
	int n, k; cin >> n >> k;

	if (n > 1 && k == n - 1) {
		cout << -1 << '\n';
		return;
	}

	k = n - k;
	int c0 = (n + 1) / 2, c1 = n / 2;

	for (int i = 1; i <= k; ++i) {
		if (i & 1) {
			if (i + 2 > k) {
				while (c0--) cout << 0;
			}
			else {
				--c0;
				cout << 0;
			}
		}
		else {
			if (i + 2 > k) {
				while (c1--) cout << 1;
			}
			else {
				--c1;
				cout << 1;
			}
		}
	}
	cout << '\n';
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int T; cin >> T;
	while (T--) work();

	return 0;
}

An element's rank from the right depends on both its position in the retained subsequence and the subsequence's final length.

Enumerate the final retained length $$$m$$$. Once $$$m$$$ is fixed, the condition for every position in the subsequence is fixed.

Whether an element can occupy the $$$j$$$-th position of the retained subsequence depends on the final length $$$m$$$, because its rank from the right is $$$m-j+1$$$.

Therefore, we enumerate the final length $$$m$$$.

For a fixed $$$m$$$, scan the original sequence from left to right and fill positions $$$1,2,\ldots,m$$$ of the subsequence in order. When filling position $$$j$$$, element $$$i$$$ can be chosen if and only if

and

Whenever the current element satisfies both conditions, choose it immediately.

To prove this greedy choice, suppose a feasible solution chooses an element $$$x$$$ for position $$$j$$$, while the greedy algorithm chooses an earlier valid element $$$y$$$. Replacing $$$x$$$ with $$$y$$$ leaves every later element of the original solution available and does not reduce the remaining suffix in which subsequent choices must be made. Thus, whenever a feasible solution exists, the greedy algorithm also succeeds.

Enumerate $$$m$$$ from $$$n$$$ down to $$$1$$$. The first feasible value is the maximum possible answer. If no positive value is feasible, the answer is $$$0$$$.

The time complexity is $$$O(n^2)$$$ per test case, and the space complexity is $$$O(n)$$$.

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

const int N = 5000;

int n;
int l[N + 10], r[N + 10], u[N + 10], v[N + 10];

bool check(int m) {
	int j = 1;

	for (int i = 1; i <= n && j <= m; ++i) {
		int x = m - j + 1;
		if ((j < l[i] || j > r[i]) && (x < u[i] || x > v[i])) ++j;
	}

	return j == m + 1;
}

void work() {
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> l[i] >> r[i] >> u[i] >> v[i];

	for (int m = n; m >= 1; --m) {
		if (!check(m)) continue;
		cout << m << '\n';
		return;
	}

	cout << 0 << '\n';
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int T; cin >> T;
	while (T--) work();

	return 0;
}

The value $$$n$$$ lies on exactly one side of every cut. Therefore, the value of the cut must be the maximum on the opposite side.

Enumerate the dividing point determined by the position of $$$n$$$. The cut values to its left must be non-decreasing, while those to its right must be non-increasing.

Merge the left sequence with the reversed right sequence. The first occurrence of a value forces its position, while every later occurrence contributes a number of choices.

First observe that no cut value can equal $$$n$$$. The value $$$n$$$ lies on exactly one side of a cut, while the maximum on the opposite side is at most $$$n-1$$$. Therefore, if some $$$a_i=n$$$, the answer is $$$0$$$.

Now consider the position of $$$n$$$. For cut $$$i$$$:

• If $$$n$$$ lies on the right, then $$$a_i$$$ is the maximum of the prefix on the left.
• If $$$n$$$ lies on the left, then $$$a_i$$$ is the maximum of the suffix on the right.

Hence, there must be a dividing point $$$c$$$ such that $$$a_1,\ldots,a_c$$$ is non-decreasing and $$$a_{c+1},\ldots,a_{n-1}$$$ is non-increasing. If both parts are non-empty, we must also have $$$a_c\ne a_{c+1}$$$. These two maxima are attained at positions on opposite sides of the dividing point, and a permutation cannot contain the same value at both positions.

We enumerate all values of $$$c$$$ satisfying these conditions. There may seem to be many candidates, but the indices belonging to both the non-decreasing prefix and the non-increasing suffix can only form a segment of equal values. Two adjacent equal values cannot form an internal boundary, so only a constant number of candidates need to be considered.

After fixing $$$c$$$, merge

with the reversed right part

to obtain one non-decreasing sequence. Process its $$$i$$$-th value $$$x$$$:

• If this is the first occurrence of $$$x$$$, then the maximum on that side must become $$$x$$$ at this position, so the assigned permutation value is forced to be $$$x$$$.
• Otherwise, we may assign any unused value smaller than $$$x$$$. Since $$$i-1$$$ values have already been used, there are $$$x-i+1$$$ choices.

For each repeated occurrence, multiply the answer by $$$x-i+1$$$. This gives the number of permutations corresponding to the fixed dividing point. Finally, sum these values over all valid dividing points.

Each merge takes $$$O(n)$$$ time. Since only a constant number of dividing points are valid, the time complexity is $$$O(n)$$$ per test case, and the space complexity is $$$O(n)$$$.