Hüsrar works as a manager at XOR Games & Toys Co. Her job is to check if a batch of products are worthy of the XOR-quality stamp.

Each toy in a batch has an ID number. When checking a batch for the XOR-quality stamp, Hüsrar looks for a subset of toys whose ID numbers' XOR sum is equal to zero. If such a subset exists, the whole batch is XOR-quality.

Ozi also works at XOR Games & Toys Co. He is responsible for the production of toys and arrangments of batches. Ozi gets in a lot of trouble when a batch of toys are not XOR-quality.

There is a faulty machine, and now Ozi needs your help!

After each toy batch is produced, each batch is put on a conveyor belt and the toy's order cannot be changed. They are inspected by Ozi first, and then sent for Hüsrar's approval.

When inspecting a toy batch, Ozi picks a number and that many (consecutive) toys are removed from the beginning of the toy line. After that, he picks another number and that many (consecutive) toys are removed from the end of the toy line. Note that not removing any toys is an option, but removing all of them is not. Ozi must remove the most toys he can, and the remaining batch must get the XOR-quality stamp from Hüsrar.

To help Ozi, given a batch of toy ID's, find the number of toys in the smallest batch that will pass Hüsrar's inspection.

Input

The first line contains integer \(\mathbf{N}\), number of toys in the batch. The next line contains integers \(\mathbf{X}_1, \ldots, \mathbf{X_N}\) separated by single spaces, ID's of the toys in the batch.

Output

Print the number of toys in the smallest batch that will pass Hüsrar's inspection. If the batch is impossible to pass Hüsrar's inspection, print -1.

Constraints

• \(1 ≤ \mathbf{N} ≤ 10^5\)
• \(1 ≤ \mathbf{X_k} ≤10^9\)

Examples

Input:

4
1 2 1 10

Output:

3

Input:

4
1 2 3 3

Output:

2

Input:

3
3 4 5

Output:

-1

Notes

In the first example, Ozi can remove the last toy and leave 1 2 1 for the inspection. After that Hüsrar chooses two 1's as the subset, where \(1 \oplus 1 = 0\), and the batch gets the XOR-quality stamp.