Условие

Курьер едет по длинному маршруту, состоящему из N последовательных участков. Для каждого участка известен его вклад в общий баланс маршрута: на одних участках курьер экономит силы и время, на других — тратит больше ресурсов. Для i-го участка этот вклад равен B[i].

Нужно разбить весь маршрут на несколько непустых подряд идущих отрезков так, чтобы сумма значений B[i] внутри каждого отрезка была одинаковой.

Курьер хочет сделать как можно меньше остановок для отчёта, поэтому его интересует минимальное количество отрезков, на которые можно разбить весь маршрут.

Определите это минимальное количество.

Если такого разбиения не существует, выведите -1.

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

Первая строка содержит одно целое число N — количество участков маршрута.

Вторая строка содержит N целых чисел B[0], B[1], ..., B[N-1] — значения участков.

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

Выведите одно целое число:

• минимальное количество отрезков, на которые можно разбить маршрут так, чтобы суммы на всех отрезках были равны;
• -1, если такого разбиения не существует.

Ограничения

• 1 <= N <= 10^7
• -10^9 <= B[i] <= 10^9

Пояснение

Разбиение должно удовлетворять всем условиям:

• каждый отрезок состоит из подряд идущих элементов;
• каждый элемент массива должен принадлежать ровно одному отрезку;
• все отрезки должны быть непустыми;
• количество отрезков должно быть не меньше двух;
• суммы элементов во всех отрезках должны быть одинаковыми.

Примеры

Пример 1

Входные данные

7
-2 4 2 1 1 -1 3

Выходные данные

2

Пример 2

Входные данные

7
2 -1 1 2 3 0 -1

Выходные данные

3

Пример 3

Входные данные

6
4 0 -2 3 0 1

Выходные данные

-1

Примечание

В первом примере маршрут можно разбить на 2 отрезка с одинаковой суммой. Также существует разбиение на 4 отрезка с одинаковой суммой, но требуется найти именно минимальное возможное количество отрезков.

Во втором примере подходящее разбиение существует только на 3 отрезка.

В третьем примере разбить маршрут на хотя бы 2 непустых подряд идущих отрезка с одинаковыми суммами невозможно.