题目描述

给出 N 个整数,求包含这 N 个整数的最短的等差数列有几项?
要求N个整数必须都在该等差数列中出现,并且保证至少存在一个等差数列包含这N个整数。


输入格式

第一行一个整数 N。

第二行包含 N 个整数,第i个整数为$A_i$。


输出格式

一行一个整数表示答案。


样例数据

输入

5
4 8 10 2 16

输出

8

备注

$2\leq N \leq 10^5, 0\leq A_i\leq 10^9$


操作

评测记录

优秀代码

信息

时间限制: 1s
内存限制: 128MB
评测模式: Normal

题解