该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

格式

输入格式

请从文件 coloring.in 读入以下数据。

第一行，输入一个正整数$n$，表示整数序列$a$的长度。 第二行，输入$n$个正整数，其中第$i$个正整数为$a_i$的值。

输出格式

请向文件 coloring.out 写入以下数据。

第一行，一个正整数，表示题目所要求的最短时间。

样例

3
2 3 9

8

2
2 999995

5

数据规范

对于30%的数据，$1≤n≤10^3$

对于100%的数据，$1≤n≤10^5,1<a_i<10^6$