Задача Счастливый билетик - 2

Описание

Назовем билетиком последовательность цифр длины n. Билетик A называется счастливым, если существует число k (1 <= k < n) такое, что сумма первых k цифр равна сумме последних n-k цифр. Число k при этом называется границей счастья.

Ваша задача - написать программу, определяющую для заданного билетика его наименьшую границу счастья, если она существует.

Формат входных данных

Первая строка входного файла содержит число n (2 <= n <= 10 ⁶ ) - длина билетика A. Во второй строке содержатся цифры a ₁ , a ₂ , ..., a _n (0 <= a _i <= 9), разделенные пробелами.

Формат выходных данных

Если билетик является счастливым, выведите его наименьшую границу счастья, в противном случае выведите "-1".