Cho một mảng gồm n số nguyên a1, a2, ..., an. Hãy tìm pivot index đầu tiên của mảng đó.

Pivot index là một vị trí trong mảng sao cho tổng tất cả các phần tử ở bên trái (không tính phần tử tại chỉ số đó) bằng với tổng tất cả các phần tử ở bên phải (không tính phần tử tại chỉ số đó).

Nếu không tồn tại chỉ số như vậy, hãy in ra -1. Nếu có nhiều chỉ số thỏa mãn, hãy in ra chỉ số nhỏ nhất (bên trái nhất).

Input:

• Dòng đầu tiên là một số nguyên n (1 ≤ n ≤ 10⁵) — số lượng phần tử của mảng.
• Dòng thứ hai gồm n số nguyên a1, a2, ..., an (|a_i| ≤ 10⁴) — các phần tử của mảng.

Output:

• In ra chỉ số pivot index đầu tiên (bắt đầu từ 0). Nếu không tồn tại, in -1.

Ví dụ:

Input:

6
1 7 3 6 5 6

Output:

3

Giải thích:

Tổng bên trái: 1 + 7 + 3 = 11
Tổng bên phải: 5 + 6 = 11
=> chỉ số pivot là 3.

Input:

3
1 2 3

Output:

-1

Giải thích:

Không tồn tại chỉ số nào sao cho tổng trái bằng tổng phải.