To solve this problem, it is necessary to guess the following fact:

Lemma: If every value of the array is either ~-1~ or ~1~ (with at least one of each) and there are more ~1~'s than ~-1~'s, there is some ~a_i=-1~ which the first operation can be used on.

This is fairly intuitive and easy to suspect. The proof is included at the bottom for the sake of completeness.

A simple corollary of this lemma is that any array with at most two distinct values can be turned into a constant array in ~\frac{N}{2}-1~ first operations and ~1~ second operation. So the first subtask can be solved in this way.

For the full points, fix some number ~x~. Construct an auxiliary array ~b~ so that ~b_i=-1~ if ~a_i \le x~ and ~b_i = 1~ if ~a_i>x~. Observe that the first operation applied to array ~a~ is applied in the same manner to array ~b~. From the first subtask's solution, we can either force ~b~ to be all ~1~ or all ~-1~. But this is the same as forcing all the elements in array ~a~ to be less than or equal to ~x~ or all the elements to be greater than ~x~.

From this observation, it becomes clear that we can binary search to force the array ~a~ to become constant. In total, at most ~\log N~ second operations are needed and at most ~\frac{N \log N}{2}~ operations are needed in total. For ~N=500~, the given constraints of ~10~ and ~2500~ are sufficient.

When implementing the solution, it is important to be able to apply the operations to ~a~ as well. A brute-force, ~\mathcal{O}(N^3 \log N + N^2 \log^2 N)~ implementation of this can pass. It is possible to improve this time complexity by using a segment tree to locate elements in ~b~ which should be changed. It may be further improved by using a segment tree of sets to quickly compute the median of a range but this is not at all necessary.

Time Complexity: ~\mathcal{O}(N^3 \log N + N^2 \log^2 N)~

Proof of Lemma: Let ~S_{i, j}~ denote the sum of the elements in the subarray from ~i~ to ~j~. Let ~k=\frac{N-2}{4}~. Assume for the sake of contradiction that there exists an array satisfying the conditions so that the first operation cannot change any ~-1~ to a ~1~. This condition is equivalent to ~a_i = -1 \implies S_{i+k+1, i+3k+1}<0~. Its contrapositive, ~S_{i+k+1, i+3k+1}>0 \implies a_i=1~ is also true.

For any index ~i~, ~S_{i+k+1, i+3k+1} + S_{i+3k+2, i+k} = S_{1, N} > 0~. So at least one of ~S_{i+k+1, i+3k+1}~ and ~S_{i+3k+2, i+k}~ must be positive, so at least one of ~a_i~, ~a_{i+2k+1}~ must be ~1~. This implies that ~a_i + a_{i+2k+1} \ge 0~ for any ~i~.

If there is only one ~i~ such that ~a_i=-1~, then there is clearly a contradiction and we are done.

Otherwise, consider the pair of indices ~(u, v)~ over all pairs of indices with ~a_u=a_v=-1~ such that ~|v - (u+2k+1)|~ is minimized (if there are multiple, pick any such pair). Let ~t = |v - (u+2k+1)|~. Note that ~t \le k~ since otherwise, ~u~ could be turned into a ~1~. Without loss of generality, say ~v = u+2k+1+t~ (rather than ~v=u+2k+1-t~). Since ~t~ is minimal, clearly ~a_{u+2k+2}=1, a_{u+2k+3}=1, \dots, a_{u+2k+t} = 1~. Now consider ~a_{u+t}, a_{u+t-1}, a_{u+t-2}, \dots, a_{u+1}~. Since ~u~ and ~v~ were chosen for ~t~ to be minimized, note that these ~t~ elements cannot equal to ~-1~ or the minimality of ~t~ would be contradicted. Thus ~a_{u+t} = a_{u+t-1} = \dots = a_{u+1} = 1~.

Let ~A = S_{v-k, v-t-1}~, ~B = S_{v+1, u-k-1}~, ~C = S_{v+k+1, u-1}~, and ~D = S_{u+t+1, u+k}~. Note that the section ~A~ describes is diametrically opposite ~C~'s section and the section ~B~ describes is diametrically opposite ~D~'s section. Since ~a_i + a_{i+2k+1} \ge 0~ for any index ~i~, ~A+C \ge 0~ and ~B+D \ge 0~. Summing these two inequalities gives ~A+B+C+D \ge 0~.

From ~a_u = -1~,

$$\displaystyle \begin{align} S_{u+k+1, u+3k+1} &\le -1 \\ S_{u+k+1, u+k+t} + S_{u+k+t+1, u+2k} + S_{u+2k+1, v} + S_{v+1, u-k-1} &\le -1 \\ S_{u+k+1, u+k+t} + S_{v-k, v-t-1} + S_{u+2k+1, v} + S_{v+1, u-k-1} &\le -1 \\ S_{u+k+1, u+k+t} + A + (t - 1) + B &\le -1 \\ A+B &\le -t-S_{u+k+1, u+k+t} \\ &\le -t+((u+k+t) - (u+k+1) + 1) \\ &= 0 \end{align}$$

Thus, ~A+B \le 0~.

Similarly, from ~a_v = -1~, we can obtain ~C+D \le 0~. Adding these two inequalities gives ~A+B+C+D \le 0~. So $$\displaystyle A+B+C+D \le 0 \le A+B+C+D.$$

This implies that ~A+B+C+D = 0~. Also, all the inequalities used to obtain this must have been equalities. This means that ~S_{u+k+1, u+k+t} = -t~ or equivalently, ~S_{u+k+1} = S_{u+k+2} = \dots = S_{u+k+t} = -1~. Also, ~a_i + a_{i+2k+1} = 0~ for all ~i~ in the sections described by ~A~, ~B~, ~C~, or ~D~.

Since ~S_{u+k+1} = -1~ and ~S_{u+t} = 1~, there is some index ~j~ where ~u+t+1 \le j \le u+k+1~ for which ~a_{j-1} = 1~ and ~a_j = -1~. But for any ~i~ between ~u+t~ and ~u+k+1~, ~a_i + a_{i+2k+1} = 0~. So ~a_{j+2k} = -1~ and ~a_{j+2k+1} = 1~. From ~a_j=-1~ and ~a_{j+2k}=-1~,

$$\displaystyle \begin{align} S_{j+k+1, j+3k+1} + S_{j+3k+1, j+k-1} &\le -2 \\ S_{1, N} + a_{j+3k+1} - a_{j+k} &\le -2 \\ S_{1, N} &\le -2 - a_{j+3k+1} +a_{j+k} \\ &\le -2 -(-1) +1 \\ &= 0 \end{align}$$

This gives ~0 < S_{1, N} \le 0~. So there is a contradiction and the lemma is true.