Андрей работает в секретной химической лаборатории, в которой производят опасную кислоту с удивительными свойствами. У Андрея есть n бесконечно больших резервуаров, расположенных в один ряд. Изначально в каждом резервуаре находится некоторое количество кислоты. Начальство Андрея требует, чтобы во всех резервуарах содержался одинаковый объем кислоты. К сожалению, разливающий аппарат несовершенен. За одну операцию он способен разлить по одному литру кислоты в каждый из первых k(1≤k≤n) резервуаров. Обратите внимание, что для разных операций k могут быть разными. Поскольку кислота очень дорогая, Андрею не разрешается выливать кислоту из резервуаров. Андрей просит вас узнать, можно ли уравнять объемы кислоты в резервуарах, и, если это возможно, то посчитать минимальное количество операций, которое потребуется, чтобы этого достичь.
Первая строка содержит число n (1≤n≤100000) — количество резервуаров. Во второй строке содержатся n целых чисел a_i (1≤a_i≤10^9), где a_i означает исходный объём кислоты в i-м резервуаре в литрах.
Если объемы кислоты в резервуарах можно уравнять, выведите минимальное количество операций, необходимых для этого. Если это невозможно, выведите «-1».