Dãy liên tiếp có tổng chia hết cho 7 (Subsequences Summing to Sevens)

Nguồn: USACO Silver

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $N$ con bò đứng liên tiếp, mỗi con có một mã số nguyên $ID_i$.

Hãy tìm độ dài lớn nhất của một đoạn bò liên tiếp sao cho tổng các mã số trong đoạn chia hết cho $7$.

Đoạn được chọn phải gồm các vị trí liên tiếp trong hàng.

Input

• Dòng đầu chứa số nguyên $N$.
• $N$ dòng tiếp theo, dòng thứ $i$ chứa mã số $ID_i$ của con bò thứ $i$.

Output

In độ dài lớn nhất của một đoạn liên tiếp có tổng mã số chia hết cho $7$.

Subtask

Điều kiện chung đã đối chiếu với nguồn:

• $1\le N\le5\cdot10^4$

• $0\le ID_i\le10^6$

• Các ID đôi một khác nhau.

• Subtask 1 — 20%: $N\le40$

• Subtask 2 — 30%: $N\le5000$.

• Subtask 3 — 50%: không có điều kiện bổ sung ngoài các điều kiện chung ở trên.

Ví dụ

Input

7
3
5
1
6
2
14
10

Output

5

Giải thích

Dãy mã số là

Đoạn từ vị trí $2$ đến vị trí $6$ có tổng

chia hết cho $7$ và có độ dài $5$.

Không có đoạn hợp lệ nào dài hơn, nên đáp án là $5$.