题目描述

希蒙坚信数字7是他的幸运数字，因此他拿到了n个数，分别是a[1],a[2],...,a[n]。现在要求一个最长的区间[x,y]，使得区间中的数(a[x],a[x+1],a[x+2],...,a[y-1],a[y])的和能被7整除。输出区间长度。若没有符合要求的区间，输出0。

输入格式

第一行输入为一个整数$N$ ($1 \leq N \leq 50,000$)表示数字个数

接下来$N$行输入行分别表示$N$个正整数（$0 \ldots 1,000,000$）

输出格式

计算出区间和为7的倍数的最长区间长度，如果找不到区间和为7的倍数时，输出0

样例 #1

样例输入 #1

7
3
5
1
6
2
14
10

样例输出 #1

5

提示

样例中, 5+1+6+2+14 = 28.