题目描述

一个双端队列里面有 $n$ 个球，每个球有一个颜色。A 和 B 玩一个游戏：

A 先手，两个人轮流操作，每次从队列的最左端或者最右端拿出一个球，如果这种颜色的球是第一次被拿出，拿出它的人获得 $1$ 分。所有球都拿完后游戏结束。

假设 A 和 B 都以最优策略操作，请求出最终得分是多少。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_{1\sim n}$ 表示从左到右每个球的颜色。

输出格式

输出一行两个以 : 隔开的整数（形如 a:b），a 表示 A 最终的得分，b 表示 B 最终的得分。

5
1 1 2 1 1

1:1

6
1 2 3 1 2 3

2:1

提示

数据范围

对于所有数据，$1\le n\le 3000$，$1\le a_i\le n$。