Transferência bancária

Existe $n$ bancos na cidade que Vasya vive, eles estão localizadas em um círculo de tal forma que bancos adjacentes estão a exatamente uma posição de diferença. Além disso, o banco $1$ e o banco $n$ são vizinhos quando $n > 1$. Nenhum banco é vizinho de si mesmo.

Vasya tem uma conta em cada banco. Seu saldo pode ser negativo, ou seja, Vasya deve dinheiro para esse banco.

Existe apenas um tipo de operação válida: transferir dinheiro de um banco qualquer para qualquer banco vizinho a ele. Não existe restrição na quantidade de dinheiro transferida de um banco para o outro.

Vasya não gosta de lidar com números grandes, por isso ela pediu para você dizer o número de operações necessárias para que o saldo de cada banco seja nulo, é garantido que é possível fazer o saldo de cada banco ser nulo, ou seja, a soma dos saldos de todos os bancos é $0$.

Entrada

A primeira linha contém um inteiro $n$ representando o número de bancos.

A segunda linha contém $n$ $(1 \leq n \leq 10^5)$ inteiros $a_i$ $(-10^9 \leq a_i \leq 10^9)$, sendo o $i$-ésimo deles o saldo do banco $i$. Ë garantido que a soma de todos os $a_i$ é $0$.

Saída

Imprima o número mínimo de operações para que o saldo de cada banco seja nulo.

 

Entrada	Saída
3 5 0 -5	1
4 -1 0 1 0	2
4 1 2 3 -6	3

Link para enviar a solução: Codeforces