Cho dãy \(A\) gồm \(N\) số nguyên được đánh số từ \(0..N−1\). Hãy tìm một chỉ số \(i\) thỏa mãn điều kiện: dãy trước \(A[i]\) và dãy sau \(A[i]\) thỏa mãn điều kiện: số lượng số chẵn/lẻ trong dãy trước bằng số lượng số chẵn/lẻ trong dãy sau. Nếu tồn tại nhiều chỉ số thỏa mãn điều kiện, in chỉ số có giá trị bé nhất. Nếu không có chỉ số nào thỏa mãn, in \(−1\).

Input

• Dòng đầu là chứa số nguyên \(N\) (\(1 \leq N \leq 10^6\)).
• Dòng thứ 2 ghi \(N\) số nguyên, các số cách nhau bởi dấu cách.

Output

• Ghi chỉ số cần tìm hoặc \(-1\) nếu không tồn tại chỉ số phù hợp.

Example

7
4 3 2 1 1 2 4

2

7
1 2 4 5 8 3 12

3