Câu 4 (3.0 điểm). Món quà dễ thương

An có một dãy số \(a_1, a_2, \dots, a_n\). An muốn chọn một số nguyên \(l\) \((1 \le l < n)\) và tách dãy thành hai phần:

• Phần đầu là dãy tiền tố độ dài \(l\): \(a_1, a_2, \dots, a_l\);
• Phần sau là dãy hậu tố độ dài \(n - l\): \(a_{l+1}, a_{l+2}, \dots, a_n\).

Món quà sẽ rất dễ thương nếu tích của các phần tử trong phần của Chi nguyên tố cùng nhau với tích của các phần tử trong phần của An, tức là ước chung lớn nhất của hai tích \(a_1 \times a_2 \times \dots \times a_l\) và \(a_{l+1} \times a_{l+2} \times \dots \times a_n\) bằng \(1\).

Tìm giá trị \(l\) nhỏ nhất sao cho món quà của An sẽ dễ thương.

Input

Vào từ tệp văn bản gift.inp:

• Dòng đầu tiên chứa số nguyên \(n\) \((2 \le n \le 10^5)\) là số phần tử của dãy số;
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) \((2 \le a_i \le 10^5)\) là các phần tử của dãy số.

Nếu không tồn tại cách cắt, in ra \(-1\).

Output

Ghi ra tệp văn bản gift.out một dòng chứa số nguyên \(l\) là vị trí mà An sẽ cắt dãy.

Example

4
2 3 4 5

3

Scoring

• 25% số test: \(2 \le n \le 10\) và \(2 \le a_i \le 10\);
• 25% số test: \(2 \le n \le 100\);
• 25% số test: \(2 \le n \le 1000\);
• 25% số test: Không có thêm ràng buộc nào.