Tổng đoạn chia hết cho 7

Cho dãy số nguyên \(a\) gồm \(n\) phần tử, các số được đánh số từ \(1\) đến \(n\). Tổng các phần tử liên tiếp của một đoạn trong dãy (kí hiệu \(Sum(l, r)\), trong đó \(1 \le l \le r \le n\)) được tính như sau: \(Sum(l, r) = a_l + a_{l+1} + \cdots + a_r\).

Độ dài của đoạn là số phần tử trong đoạn.

Yêu cầu: Tìm đoạn dài nhất có tổng các phần tử chia hết cho \(7\).

Input

• Dòng đầu ghi số nguyên dương \(n\) (\(1 \le n \le 50000\)).
• Dòng thứ hai ghi \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(0 \le a_i \le 10^6\)), các số cách nhau một dấu cách.

Output

Ghi ra số lượng phần tử của đoạn dài nhất tìm được. Nếu không có đoạn nào thỏa mãn thì ghi \(0\).

Scoring

• Có \(50\%\) số điểm với \(1 \le n \le 2000\).
• Có \(50\%\) số điểm với \(2000 < n \le 50000\).

Sample Input 1

7
3 5 1 6 2 14 10

Sample Output 1

5