Divisibilidade de Subvetor

Dado um vetor de $n$ inteiros, sua tarefa é contar a quantidade de subvetores onde a soma de seus valores é divisível por $n$.

Lembre-se que um subvetor é um intervalo contíguo de elementos de um vetor.

Entrada:

A primeira linha de entrada o inteiro $n$, o tamanho do vetor.

A segunda linha de entrada contém $n$ inteiros $a_1, a_2, ..., a_n$, os valores do vetor.

Saída

Imprima um inteiro: o número de subvetores distintos onde a soma de seus valores é divisível por $n$.

Restriçoes:

• $1 \leq n \leq 2*10^5$
• $-10^9 \leq a_i \leq 10^9$

Exemplos:

5
3 1 2 7 4

1

Nota:

O subvetor $[1, 2, 7]$ tem soma $10$, por tanto tem soma divisível por $5$. Esse é o único subvetor válido.

Para submeter sua solução use esse link.