题意化简

给定一个数组，求选择出一个 最长的 公差为 $k$ 的等差数列。如果有多个这样的等差数列，选择起点最小的那个。

思路:哈希表 + 枚举 + 同余

1.如何判断两个数是否处在同一个间隔为k的等差数列中？

他们同时对k取模，得到这个序列的最小非负整数，如果相等，则处于同一个等差序列。这样我们只需要用哈希表统计a[i] % k的个数。

题目内容

给定一个整数数组$nums$，同时给定一个整数$interval$。

指定数组$nums$中的某个元素作为起点，然后以$interval$ 为间隔递增，如果递增的数（包含起点）等于$nums$中的元素，则数组$nums$中对应的元素消除，返回消除元素最多的起点元素。如果消除的元素同样多，则返回最小的起点元素。

输入描述

输入格式：

第一行输入整数数组的长度$n$

第二行输入长度为$n$的整数数组$nums$

第三行输入整数$interval$

$1＜=n＜=10^5$

$0＜=nums[i]＜=10^8$

$0＜=interval＜=10^5$

输出描述

起点元素的最小值

样例1

输入

6
4 5 7 1 1 2
3

输出

1

说明

输入给定的间隔为$3$，如果以元素$1$为起点，则可以消除$1,4,7,10,...$这些元素，因此，我们可以消除给定数组中的$4,7,1,1$这$4$个元素，以其他元素为起点也没有办法消除更多元素了，因此返回$1$

样例2

输入

5
4 5 7 1 2
50

输出

1

说明

输入给定的间隔为$50$,如果以元素$1$为起点，则可以消除$1,51,101$这些元素，因此，我们可以消除给定数组中的$1$这个元素，同理，如果以$2$为起点，则可以消除$2,52,102$这些元素，因此我们可以消除给定数组中的$2$这个元素，以此类推，无论以哪个元素作为起点，都只能消除$1$个元素，因此返回最小的起点元素$1$。