Lệch nhỏ nhất

Cho dãy số nguyên dương \(A_1, A_2, A_3, \ldots, A_n\). Tìm hai số có giá trị khác nhau trong dãy có tổng chẵn và chênh lệch giữa hai số đó là nhỏ nhất.

Input

Dữ liệu vào gồm \(2\) dòng:

• Dòng thứ nhất chứa số nguyên \(n\) (\(2 \le n \le 3 \times 10^5\)).

• Dòng thứ hai chứa \(n\) số nguyên dương \(A_1, A_2, \ldots, A_n\) (\(A_i \le 10^8\) với mọi \(i = 1, 2, \ldots, n\)).
  Các số trên một dòng được ghi cách nhau một dấu cách.

Ràng buộc:

• Subtask 1 (\(3{,}6\) điểm): \(n \le 1000\) và tất cả các số đều là số chẵn.

• Subtask 2 (\(1{,}2\) điểm): \(n \le 1000\).

• Subtask 3 (\(1{,}2\) điểm): \(n \le 3 \times 10^5\).

Output

In ra một số nguyên dương duy nhất là chênh lệch nhỏ nhất giữa hai số tìm được. Ghi ra \(-1\) trong trường hợp không tồn tại.

Example 1

Input:

4
1 3 7 9

Output:

2

Example 2

Input:

4
9 10 1 6

Output:

4

Note

Ví dụ 1: Hai số tìm được là \((1, 3)\) hoặc \((7, 9)\) đều có chênh lệch là \(2\).

Ví dụ 2: Hai số tìm được là \((10, 6)\) có chênh lệch là \(4\).