Description

给你n个数，分别是a[1],a[2],...,a[n]。

求一个最长的区间[x,y]， 使得区间中的数(a[x],a[x+1],a[x+2],...,a[y-1],a[y])的和能被7整除。

输出区间长度。若没有符合要求的区间，输出0。

Format

Input

第一行给出数字N，1≤N≤50,000

接下来N个数字，值在[0…1,000,000]

Output

如题

Samples

7
3
5
1
6
2
14
10

5

Hint

选取区间

[5,1,6,2,14]

其总和为7的倍数