题目描述

译自 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$ 的得分。

---

样例 1

输入

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$。

---

样例 2

输入

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

---