XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: lista.x, onde x deve ser c, cpp, java, js ou py

Lista palíndroma

Uma palavra é chamada de palíndromo se a primeira letra da palavra é igual à última letra da palavra, a segunda letra é igual à penúltima letra, a terceira letra é igual à antepenúltima letra, e assim por diante. Por exemplo, as palavras osso e sopapos são palíndromos.

Nesta tarefa estamos interessados não em palavras, mas em listas de números inteiros. Nesse caso, vamos definir que uma lista é palíndroma se L[i] = L[N-i+1], onde L[i] representa o i-ésimo elemento da lista (note que nesta notação o índices variam de 1 a N).

Você pode modificar uma lista usando a operação de contração, que é definida da seguinte forma: escolha dois elementos adjacentes da lista e substitua os dois elementos por um único elemento de valor igual à soma dos elementos substituídos. Note que ao efetuar uma operação de contração o número de elementos da lista decresce de um elemento.

Dada uma lista de números inteiros, você deve escrever um programa para determinar o menor número de operações de contração que devem ser realizadas de modo que a lista resultante seja palíndroma.

Entrada

A primeira linha da entrada contém um inteiro N, o número de elementos da lista. A segunda linha contém N inteiros Li, os elementos da lista.

Saída

Seu programa deve produzir uma única linha, contendo um único inteiro, o menor número de operações de contração necessárias para tornar a lista palíndroma.

Restrições

  • 1 ≤ N ≤ 106
  • 1 ≤ Li ≤ 109, para 1 ≤ i ≤ N

Informações sobre a pontuação

  • Para um conjunto de casos de testes valendo 30 pontos, N ≤ 10.
  • Para um conjunto de casos de testes valendo outros 30 pontos N ≤ 103.
  • Para um conjunto de casos de testes valendo outros 40 pontos, nenhuma restrição adicional.

Exemplos

Entrada
5
10 60 20 40 10
Saída
1
	

 

Entrada
5
999 1 999 1 999
Saída
0
	

 

Entrada
4
10 40 30 20
Saída
2
	

 

Tarefas Programação Nível 1
Promoção
logo sbc
Patrocínio
Apoio
Coordenação