Cho một dãy số nguyên dương ~a_1, a_2, \dots, a_n~. Một đoạn con liên tiếp ~a_l, a_{l+1}, \dots, a_r~ được gọi là đoạn con đẹp nếu thỏa mãn tổng ~S = a_l + a_{l+1} + \dots + a_r~ chia hết cho số lượng ước dương của ~a_r~.

Yêu cầu: Hãy đếm xem có bao nhiêu đoạn con liên tiếp trong dãy đã cho là đoạn con đẹp.

Input

Dòng đầu tiên ghi số nguyên dương ~n~ ~(n \le 10^4)~; Dòng thứ hai ghi ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ ~(a_i \le 10^6)~.

Output

Ghi ra một số nguyên duy nhất là số lượng đoạn con đẹp trong dãy đã cho.

Sample Input 1

5
1 2 3 4 5

Sample Output 1

6

Giải thích

• Dãy đẹp chỉ gồm một phần tử: ~\{1\}~, ~\{2\}~;
• Dãy đẹp gồm ba phần tử: ~\{1, 2, 3\}~, ~\{2, 3, 4\}~, ~\{3, 4, 5\}~;
• Dãy đẹp gồm bốn phần tử: ~\{2, 3, 4, 5\}~.

Subtasks