题目描述

译自 COCI 2023/2024 Contest #2 T4「Kuglice」

圣诞节，一年中最美好的时刻就要来了。我们的主人公，Marin 和 Josip 已经从圣诞购物回来，开始装饰他们的圣诞树。

他们买了 $n$ 件圣诞饰品，这些饰品相邻摆放在一个长盒子里，第 $i$ 件饰品的颜色是 $a_i$。盒子两边都是打开的，因此可以从盒子的左右两边取出饰品。盒子是透明的，所以 Marin 和 Josip 可以看到每个装饰品的颜色。

上图显示了第二个样例中盒子的初始状态。对于第一步，Marin 可以从盒子的左端抽出颜色 $1$ 的饰品，也可以从盒子的右端抽出颜色 $3$ 的饰品。

Josip 想出了一个游戏，可以让装饰圣诞树变得更加有趣，尽管装饰圣诞树本身已经很有趣了。游戏规则如下：Marin 和 Josip 轮流操作，Marin 先手。玩家依次从盒子里抽出一个饰品（从盒子的左端或右端），然后放到圣诞树上。如果抽到的饰品的颜色之前还没有被抽到过，则该玩家得一分。当从盒子中抽出最后一个饰品时，游戏结束。

游戏的获胜者是得分较多的一方，因此 Marin 和 Josip 都希望最大限度地提高自己的得分。由于两人都是出色的玩家，他们会以最佳方案进行游戏。你的任务是在游戏结束时输出结果。

输入格式

第一行一个整数 $n\ (1\le n\le 3\ 000)$，表示盒子中饰品个数。

第二行包含 $n$ 个整数 $a_i\ (1\le a_i\le n)$，表示盒子中每个饰品的颜色。

输出格式

输出一行表示游戏结果，即两个用字符 : 连接的整数，两个整数分别表示 Marin 和 Josip 的得分。

5
1 1 2 1 1

1:1

Marin 先手，他从盒子左边抽出颜色 $1$ 的饰品。Marin 得一分。

Josip 从盒子右端抽出颜色 $1$ 的饰品，但是他不得分，因为颜色 $1$ 的饰品已经被抽出来过了。

Marin 从盒子左端抽出颜色 $1$ 的饰品，但是他也不得分，因为颜色 $1$ 的饰品已经被抽出来过了。

Josip 从盒子左端抽出颜色 $2$ 的饰品。这是颜色 $2$ 的饰品第一次被抽出来，所以 Josip 得一分。

Marin 抽出最后一个（颜色 $1$）饰品，但他不得分，游戏结束。

Marin 总共得一分（他首次把颜色 $1$ 的饰品抽出来），Josip 也总共得一分（他首次把颜色 $2$ 的饰品抽出来）。最终结果为 $1:1$。

6
1 2 3 1 2 3

2:1

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务编号	附加限制	分值
$1$	对于所有 $i=1,\ldots,n$，满足 $a_i\le 2$	$15$
$2$	$n\le 20$	$9$
$3$	对于所有 $i=1,\ldots,n$，满足$a_i\le 20$	$24$
$4$	$n\le 300$	$14$
$5$	无附加限制	$38$