圣诞节临近，这是一年中最美好的时光。我们的主角 Marin 和 Josip 结束了圣诞购物，开始装饰他们的圣诞树。
他们买了一个长条形的盒子，里面并排装着 $n$ 个圣诞装饰品，第 $i$ 个装饰品的颜色为 $a_i$。盒子两端都是开口的，因此装饰品可以从盒子的左侧或右侧取出。盒子是透明的，所以 Marin 和 Josip 可以看到每个装饰品的颜色。
插图展示了第二个样例中盒子的初始状态。在第一步中，Marin 可以选择从盒子左端取出一个颜色为 1 的装饰品，或者从右端取出一个颜色为 3 的装饰品。
Josip 想出了一个游戏，让装饰圣诞树变得更有趣，尽管装饰本身就已经很有趣了。游戏规则如下：Marin 和 Josip 轮流行动，Marin 先手。轮到行动的玩家从盒子中取出一个装饰品（从左端或右端），并将其挂在树上。如果取出的装饰品颜色是之前从未被取出过的，该玩家得一分。当盒子里的最后一个装饰品被取出时，游戏结束。
游戏的获胜者是得分更高的玩家，因此 Marin 和 Josip 都希望最大化自己的得分。由于他们都是优秀的玩家，他们会采取最优策略。你的任务是输出游戏结束时的结果。
输入格式
第一行包含一个整数 $n$ ($1 \le n \le 3000$)，表示盒子中装饰品的数量。 第二行包含 $n$ 个整数 $a_i$ ($1 \le a_i \le n$)，表示盒子中装饰品的颜色。
输出格式
在唯一的一行中，输出游戏的结果，即两个数字，中间用字符 ':' 连接（不含引号），分别表示 Marin 和 Josip 的得分。
子任务
| 子任务 | 分值 | 数据范围 |
|---|---|---|
| 1 | 17 | $a_i \le 2$ 对于所有 $i = 1, \dots, n$ |
| 2 | 10 | $n \le 20$ |
| 3 | 26 | $a_i \le 20$ 对于所有 $i = 1, \dots, n$ |
| 4 | 15 | $n \le 300$ |
| 5 | 42 | 无附加限制 |
样例
输入 1
5 1 1 2 1 1
输出 1
1:1
说明 1
Marin 先手，他从盒子左端取出一个颜色为 1 的装饰品。Marin 得一分。 Josip 从盒子右端取出一个颜色为 1 的装饰品，但他没有得分，因为颜色为 1 的球已经被取过了。 Marin 从盒子左端取出一个颜色为 1 的装饰品。他也没有得分，因为颜色为 1 的球已经被取过了。 Josip 从盒子左端取出一个颜色为 2 的装饰品。这是第一个被取出的颜色为 2 的球，所以 Josip 得一分。 Marin 从盒子左端取出最后一个装饰品（颜色为 1），但他没有得分，游戏结束。 Marin 总共得 1 分（他第一个取出了颜色为 1 的装饰品），Josip 也总共得 1 分（他第一个取出了颜色为 2 的装饰品）。 最终结果为 1:1。
输入 2
6 1 2 3 1 2 3
输出 2
2:1