Cho số nguyên \(n \) và dãy số nguyên \(a_1,a_2,…,a_n. \)

Một đoạn con \([L,R]\) của dãy là một dãy con gồm các phần tử liên tiếp \(a_L,a_(L+1),..,a_R\) với \(1≤L<R≤n. \)

Độ dài của đoạn con \([L,R]\) bằng \(R-L+1. \)

Đoạn con \([L,R]\) được gọi là đẹp nếu số lượng các số nguyên tố trong đoạn bằng số lượng các số không nguyên tố trong đoạn đó.

Yêu cầu: Tìm đoạn con đẹp có độ dài lớn nhất.

Input

• Dòng thứ nhất chứa số nguyên \(n (1≤n≤10^6).\)

• Dòng thứ hai chứa \(n \) số nguyên \(a_1,a_2,…,a_n (|a_i |≤10^6,1≤i≤n).\)

Giữa các số trên cùng một dòng cách nhau dấu cách.

Output

• Ghi độ dài lớn nhất của đoạn con đẹp tìm được.

Ràng buộc

• Subtask 1: 30% test với \(n≤10^2.\)

• Subtask 2: 30% test với \(n≤10^3.\)

• Subtask 3: 40% test với \(n≤10^6.\)

Sample Input

7
10 3 4 4 2 5 8

Sample Output

4

Giải thích: Đoạn con dài nhất thỏa [3 4 4 2] có hai số nguyên tố 3, 2 và hai số không nguyên tố 4, 4.