FRAKTAL - konkurs programistyczny

Jaś pomagał zbierać jabłka w pobliskim sadzie. Właścicielka sadu zaprowadziła chłopca do magazynu, gdzie w ciągu stało n butelek soku jabłkowego. Następnie powiedziała mu, że w podziękowaniu za wykonaną pracę może wybrać sobie niepusty, spójny podciąg butelek.

Nasz bohater bardzo się ucieszył. Postanowił, że sok z otrzymanych butelek przeleje do odpowiednio dużego zbiornika, a następnie będzie go sprzedawał. Do odmierzania porcji Jaś chce użyć jednej z opróżnionych butelek. Ponieważ nie wie jeszcze, którą wybierze zależy mu na tym, żeby suma pojemności otrzymanych butelek była podzielna przez pojemność każdej z nich.

Odpowiedz na pytanie. Na ile sposobów Jaś może wybrać niepusty, spójny podciąg butelek, tak aby suma ich pojemności była podzielna przez pojemność każdej z nich?

Wejście

W pierwszej linii wejścia znajduje się jedna liczba całkowita n ∈ [1, 1000] oznaczająca liczbę butelek stojących w ciągu. W drugiej linii wejścia znajduje się n liczb całkowitych z przedziału [1, 10⁹] określających ich pojemności.

Wyjście

Na wyjściu należy wypisać na ile sposobów Jaś może wybrać niepusty, spójny podciąg butelek, tak aby suma ich pojemności była podzielna przez pojemność każdej z nich.

Przykład

Wejście:

5
3 2 4 2 5

Wyjście:

6