Anh có một dãy số gồm ~N~ phần tử ~a_1, a_2, \ldots, a_N~ thỏa mãn ~a_i \le a_{i+1}~ với mọi ~i < N~. Đây là một dãy không giảm, và Anh thì không thích điều đó. Anh có thể thay đổi dãy số này bằng cách chọn 2 số liền kề, xóa chúng khỏi dãy và chèn vào vị trí đó một số mới bằng ~x \oplus y~ (với ~x, y~ là hai số được chọn, ~\oplus~ là phép toán XOR). Thao tác này được gọi là REPXOR.

Anh muốn dãy số của mình không còn là một dãy không giảm nữa, và Anh có thể thực hiện thao tác REPXOR nhiều lần. Tuy nhiên, Anh muốn thực hiện ít lần REPXOR nhất có thể.

Hãy giúp Anh tìm ra số lần thực hiện REPXOR ít nhất để dãy số không còn là dãy không giảm.

Dữ liệu

• Dòng đầu gồm số nguyên dương ~N~ là độ dài của dãy ~(1 \le N \le 5 \times 10^5)~.

• Dòng tiếp theo gồm ~N~ số nguyên dương ~a_1, a_2, \ldots, a_N~ ~(1 \le a_i \le 10^9,\ a_i \le a_{i+1})~.

Kết quả

Gồm một số nguyên duy nhất là số thao tác mà Anh thực hiện ít nhất để dãy không còn là dãy không giảm. Nếu như không có cách nào để thay đổi thì xuất -1.

Ví dụ

Sample Input 1

4
2 5 6 8

Sample Output 1

1

Sample Input 2

3
1 2 3

Sample Output 2

-1

Sample Input 3

5
1 2 4 6 20

Sample Output 3

2

Giải thích

• Ở ví dụ thứ nhất, Anh có thể chọn ~2, 5~ để thực hiện REPXOR, dãy mới được tạo thành là ~7, 6, 8~.

• Ở ví dụ thứ hai, mọi dãy có thể tạo ra bằng các thao tác REPXOR đều vẫn là dãy không giảm, nên đáp án là ~-1~.

• Ở ví dụ thứ ba, đầu tiên anh chọn ~1, 2~ để thực hiện REPXOR, dãy mới được tạo thành là ~3, 4, 6, 20~. Sau đó, Anh thực hiện REPXOR cho 2 số là ~3, 4~ và tạo được một dãy mới là ~7, 6, 20~. Anh chỉ cần dùng 2 thao tác để khiến dãy không còn là dãy không giảm. Đây cũng là cách tốt nhất.