Problem Description

There are $n$ balls in a deque, and each ball has a color. A and B play a game:

A goes first. The two players take turns. Each turn, a player removes one ball from either the left end or the right end of the deque. If this color is removed for the first time, the player who removed it gets $1$ point. The game ends after all balls are removed.

Assuming both A and B play optimally, please determine the final scores.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers $a_{1\sim n}$, representing the colors of the balls from left to right.

Output Format

Output one line with two integers separated by : (in the form a:b). Here, a is A's final score, and b is B's final score.

5
1 1 2 1 1

1:1

6
1 2 3 1 2 3

2:1

Hint

Constraints

For all testdata, $1\le n\le 3000$ and $1\le a_i\le n$.

Translated by ChatGPT 5