Christmas time is approaching, the most beautiful time of the year. Our protagonists, Marin and Josip, have returned from Christmas shopping and have started decorating their Christmas tree.

They bought $n$ Christmas ornaments arranged next to each other in an elongated box, and the $i$-th ornament has color $a_i$. The box is open on both sides, so the ornaments can be taken out from both the left and the right side of the box. The box is transparent, so Marin and Josip can see the color of each ornament.

The illustration shows the initial state of the box in the second example. On his first move, Marin can draw either an ornament of color $1$ from the left end of the box or an ornament of color $3$ from the right end of the box.

Josip came up with a game that would make decorating the tree even more fun, although it's already a lot of fun by itself. The game works as follows: Marin and Josip take turns, and Marin starts the game. The player in turn draws an ornament from the box (either from the left or the right end of the box) and places it on the tree. If they draw an ornament whose color has not been drawn yet, the player scores a point. The game ends when the last ornament is drawn from the box.

The winner of the game is the player who has scored more points, so both Marin and Josip want to maximize their number of points. Since both of them are excellent players, they will play optimally. Your task is to print the result at the end of the game.

Input Specification

The first line contains an integer $n$ $(1\le n\le 3000)$, the number of ornaments in the box.

The second line contains $n$ integers $a_i$ $(1\le a_i\le n)$, the colors of the ornaments in the box.

Output Specification

In the first and only line, print the result of the game: two numbers separated by the character :, Marin's and Josip's scores.

Constraints

Subtask	Points	Constraints
1	17	$a_i\le 2$ for all $i=1,\dots ,n$
2	10	$n\le 20$
3	26	$a_i\le 20$ for all $i=1,\dots ,n$
4	15	$n\le 300$
5	42	No additional constraints.

Sample Input 1

5
1 1 2 1 1

Sample Output 1

1:1

Explanation for Sample 1

Marin is first, and he draws an ornament of color $1$ from the left end of the box. Marin scores a point.

Josip draws an ornament of color $1$ from the right end of the box, but he does not score a point because a ball of color $1$ has already been drawn.

Marin draws an ornament of color $1$ from the left end of the box. He does not score a point either because a ball of color $1$ has already been drawn.

Josip draws an ornament of color $2$ from the left end of the box. This is the first ball of color $2$ drawn, so Josip scores a point.

Marin draws the last ornament (color $1$) from the left end of the box, but it does not earn him a point, and the game ends.

Marin has a total of $1$ point (he drew the ornament of color $1$ first), and Josip also has a total of $1$ point (he drew the ornament of color $2$ first).

The final result is $1:1$.

Sample Input 2

6
1 2 3 1 2 3

Sample Output 2

2:1