Question
Subarrays with Sum Divisible by Length
You are given an array of KaTeX can only parse string typed expression integers. Your task is to count the number of subarrays such that the sum of the subarray is divisible by the length of that subarray.
Input
The first line contains a single integer KaTeX can only parse string typed expression — the size of the array.
The second line contains KaTeX can only parse string typed expression integers, representing the elements of the array — KaTeX can only parse string typed expression.
The second line contains KaTeX can only parse string typed expression integers, representing the elements of the array — KaTeX can only parse string typed expression.
Output
Print a single integer — the number of subarrays whose sum is divisible by their length.
Example
Input
5
1 2 3 4 5
Output
9
Explanation
Valid subarrays:
Length 1:
[1], [2], [3], [4], [5] → All sums divisible by 1 → 5 subarrays
Length 3:
[1, 2, 3] → sum = 6, divisible by 3
[2, 3, 4] → sum = 9, divisible by 3
[3, 4, 5] → sum = 12, divisible by 3 → 3 subarrays
Length 5:
[1, 2, 3, 4, 5] → sum = 15, divisible by 5 → 1 subarray
Total = 5 + 3 + 1 = 9
5
1 2 3 4 5
Output
9
Explanation
Valid subarrays:
Length 1:
[1], [2], [3], [4], [5] → All sums divisible by 1 → 5 subarrays
Length 3:
[1, 2, 3] → sum = 6, divisible by 3
[2, 3, 4] → sum = 9, divisible by 3
[3, 4, 5] → sum = 12, divisible by 3 → 3 subarrays
Length 5:
[1, 2, 3, 4, 5] → sum = 15, divisible by 5 → 1 subarray
Total = 5 + 3 + 1 = 9