Farmer John tem $N$ vacas, $2 \le N \le 20$; a vaca $i$ produz $M(i)$ unidades de leite ao dia ($1 \le M(i) \le 100,000,000$). Para agilizar a ordenha diária instala uma máquina nova no celeiro. Mas é sensível demais: só funciona se as vacas à esquerda e à direita produzem exatamente o mesmo total!
Um subconjunto é «balanceado» se pode ser dividido em dois grupos de produção igual. Só um balanceado faz a máquina funcionar, e FJ quer contar esses subconjuntos das $N$ vacas. Calcule o número.
Entrada
- Linha 1: inteiro $N$.
- Linhas 2..1+$N$: a linha $i+1$ contém $M(i)$.
Saída
- Linha 1: número de subconjuntos balanceados.
Exemplos
Entrada 1
4 1 2 3 4
Saída 1
3
Nota
Quatro vacas produzem 1, 2, 3 e 4 unidades.
Três subconjuntos balanceados: $\{1,2,3\}$ divide-se em $\{1,2\}$ e $\{3\}$; $\{1,3,4\}$ em $\{1,3\}$ e $\{4\}$; $\{1,2,3,4\}$ em $\{1,4\}$ e $\{2,3\}$.
Autor do problema: Neal Wu, 2012