Lập trình nhập vào một số nguyên dương \(N\) và dãy số nguyên \(A\) gồm \(N\) phần tử. Hãy tìm kích thước mảng con lớn nhất có \(GCD\) chính xác bằng \(1\).

INPUT FORMAT

Dòng đầu là số nguyên dương \(N\) \((1 \leq N \leq 10 ^5)\).

Dòng thứ hai là dãy số nguyên \(A\) \((1 \leq A_i \leq 10^5)\).

OUTPUT FORMAT

In ra kích thước mảng con lớn nhất có \(GCD\) bằng \(1\). Nếu không có đáp án hãy in ra \(-1\)

Ví dụ:

Input

3
2 3 5

Output

3

Ví dụ:

Input

3
3 18 12

Output

-1

Giải thích ví dụ mẫu:

• Ví dụ 1: (2 3 5)

  • Toàn bộ dãy số có GCD bằng 1, nên kích thước mảng con lớn nhất là 3.

• Ví dụ 2: (3 18 12)

  • GCD của toàn bộ dãy số là 3, không có mảng con nào có GCD bằng 1, nên kết quả là -1.
    

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House