Freight Manifest Digit-Balanced Runs

A freight yard numbers the boxcars of a train from 1 to n, front to back. Each boxcar i carries nums[i] tonnes of cargo. For any contiguous run of boxcars [l, r] (1 <= l <= r <= n), define its total weight as the sum of nums[l] through nums[r]. A yard inspector calls the run [l, r] "digit-balanced" if the sum of the decimal digits of the run's total weight is exactly equal to the sum of the decimal digits of l plus the sum of the decimal digits of r (for example, the digit sum of 108 is 1+0+8=9, and the digit sum of 0 is 0). Count how many digit-balanced runs exist in the train.

Input format

• Line 1: an integer n, the number of boxcars.
• Line 2: n space-separated integers, nums[1] through nums[n] — the cargo weight of each boxcar, in order.

Output format

Print a single integer: the total number of digit-balanced runs [l, r] (over all 1 <= l <= r <= n).

Constraints

• 1 <= n <= 400
• 0 <= nums[i] <= 10000 for every boxcar i
• Positions l and r refer to the 1-indexed boxcar numbering described above (both range from 1 to n).

4
2 3 100 5

1

2
1 1

0