Cho số nguyên dương \(n\) và dãy số nguyên \(a_0,a_1,…,a_{n-1}.\)

Yêu cầu: Hãy tìm chỉ số \(i\) thỏa mãn điều kiện số lượng số chẵn trước \(i\) bằng số lượng số chẵn sau \(i\), hoặc số lượng số lẻ trước \(i\) bằng số lượng số lẻ sau \(i\). Nếu không có chỉ số nào thỏa mãn ghi -1.

Input:

• Dòng đầu chứa số nguyên \(n (n≤10^6 ).\)

• Dòng thứ hai ghi \(n\) số nguyên \(a_0,a_1,…,a_{n-1} (a_i≤10^9 ).\)

Output:

• • Nếu có nhiều chỉ số thỏa mãn ghi chỉ số nhỏ nhất tìm được. Nếu không có chỉ số nào tồn tại, in ra -1

sample Input

6
4 3 2 1 1 2 4

Sample Output

2