For this problem, one first step is to consider the checker: how do we check that an answer is correct? How do we count the number of even subarrays?

The answer is semi-well-known. You might be able to find the answer on the internet, or you may have already solved a problem that tests this. At any rate, the basic idea is to keep track of the number of even prefixes and number of odd prefixes.

At the start, you have an even prefix of zero elements. Then, for each element, if the new prefix is even, any even prefix already seen can be used to make an even subarray, and if it is odd, any odd prefix can be used.

The reason for this is that if you have two prefixes, the space in the longer one but not the shorter one is a subarray. We include the zero length prefix to make sure we get all the prefixes. In order for the subarray formed to have even sum, the sums of the two prefixes have to have the same parity.

At this point, you may realize that it does not matter as to the position of the prefixes, but rather only the number of even prefixes and the number of odd prefixes. Specifically, if we have ~A~ even prefixes, ~B~ odd ones, and we define:

$$\displaystyle T(x) = \frac{x(x-1)}{2}$$

Then the number of even subarrays is ~T(A) + T(B)~. We have at least one even prefix.

First Subtask

For the first subtask, we can brute force all ~A, B \le 2000~ to get the number of even prefixes and odd prefixes. From there we can make a PSA and reverse it to get our original array. We remark that the original array can be constructed such that it has at most one odd number in all cases.

Time Complexity: ~\mathcal O(N^2)~

Second Subtask

For full marks, we can use a two-pointer approach. Iterate through all ~A \le 10^6~ in increasing order and constantly decrease ~B~ until we either find ~T(A) + T(B) = K~ and ~A + B \le 10^6 + 1~, or output ~-1~. Contestants should take care to handle ~K = 0~ and ~K = T(10^6 + 1)~ properly. The former should have ~N = 1~, and the latter has a solution when the whole array is even and ~N = 10^6~.

Time Complexity: ~\mathcal O(N)~