格式

输入格式

请从文件 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$