Rice Bags

All bags have pairwise distinct rice counts. Choose at least two bags such that, after sorting in ascending order, the square of each item equals exactly the next item. Return the maximum number of bags that can be chosen, or −1 if there is no solution.

输入格式

The first line contains n, and the second line contains n distinct integers. The original bounds 1≤n≤200000 and 2≤riceBags[i]≤10^6 are restored; the incorrect constraint spliced together by HTML cleanup must not be used.

输出格式

Output a single integer answer.

样例 1

输入：

3
2 4 16

输出：

3

样例 2

输入：

3
2 3 5

输出：

-1

样例 3

输入：

2
1000 1000000

输出：

2

样例说明

The outputs of the three public examples are, in order: 3; -1; 2. Verified by independent enumeration or direct simulation.