Kuglice (Christmas Ornaments)

Christmas time is approaching, the most beautiful time of the year. Marin and Josip have returned from their Christmas shopping and 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 the color $a_i$. The box is open on both sides, so ornaments can be taken out from both the left and the right end. The box is transparent, so Marin and Josip can see the color of each ornament.

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

Marin and Josip take turns, and Marin starts. The player in turn draws an ornament from either the left or the right end of the box and places it on the tree. If the color has not been drawn yet, the player scores a point. The game ends when the last ornament is drawn. The player with more points wins, so both players try to maximize their own points. Both play optimally. Print the result at the end of the game.

The first line contains an integer $n$ ($1 \le n \le 3\,000$), 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.

Print one line with two numbers connected by the character :, Marin's score and Josip's score.

In the first move, Marin takes an ornament of color $1$ from the left end and scores a point. Josip takes an ornament of color $1$ from the right end, but he scores nothing because color $1$ was already drawn. Marin takes another ornament of color $1$ from the left end and scores nothing. Josip takes an ornament of color $2$ from the left end, the first one of that color, so he scores a point. Marin takes the last ornament (color $1$) from the left end, scores nothing, and the game ends. Marin has 1 point and Josip has 1 point, so the result is 1:1.