Hello everyone This problem was one of the problems in the ECPC qualifications, and I couldn't think of an efficient way to solve it.

We are given an array a of n integer, and an integer k. Next, we will have q queries, each query has L R. We need to answer the following question for each query: How many subarrays in the range L to R (inclusive) where sum of each subarray is equal to K?

To be honset I couldn't find a good solution to this problem. So I would appreciate your help.

Input:
n = 10 k = 5
a = {2 3 0 0 0 2 3 1 1 0}
7
1 2
1 3
1 7
1 10
2 7
2 6
3 8

Output:
1
2
9
11
5
1
4