Prepared by: Fran Babić

In the first subtask, it holds that there are at most two different colors in the sequence. The first ball taken will definitely score ~1~ point (for Marin), so the only possible outcomes are 1:0, 1:1, and 2:0. Solving the first subtask boils down to decomposing it into 3 different cases:

1. All elements in the sequence are the same, i.e., the number of different colors is one.
   In this case, the game result will be 1:0.
2. The element at the left end of the sequence is different from the one at the right end, i.e., ~a_1 \ne a_n~.
   Whichever element Marin chooses in the first move, Josip can take the one from the other end of the sequence, which is different from the one Marin took. We can see that in this case, the game result will be 1:1.
3. Not all elements in the sequence are the same, and the elements at the ends of the sequence are the same (~a_1 = a_n~).
   It is easy to see that the answer will depend on the parity of the longest prefix and suffix of equal elements.

Let ~L_i = \min_{a_j=i} j~ and ~R_i = \max{a_j=i} j~, i.e., the index of the first occurrence and the index of the last occurrence of a color ~i~ in the sequence. Consider some game state ~(l, r)~ where ~l~ is the index of the leftmost ball in the box, and ~r~ is the index of the rightmost ball in the box. For a complete solution, we need the following observation:

Observation. For the current game state ~(l, r)~, a ball of color ~i~ has been taken in some previous moves if and only if ~L_i < l~ or ~R_i > r~.

Using this, we can write a function ~f(l, r)~ that returns the difference in points between the first and second player in that game state. The value returned by ~f(l, r)~ depends on the values of ~f(l+1, r)~ and ~f(l, r-1)~. The complexity of such an algorithm is ~\mathcal O(2^n)~, but by memoizing the function, we reduce the complexity to ~\mathcal O(n^2)~, which is sufficient to score all of the points.