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