652. Pastries in Hawen
0
Medium
In the town of Hawen, there are N shops that sell Pastries. Each shop sells pastries with different taste levels. Dhruv wants to have pastries with a total taste value of K. However, he can only have pastries from consecutive shops, meaning he cannot skip any shops in between. For example, if there are 5 shops numbered 1, 2, 3, 4, 5, then eating from 1-3-4 would not be a valid choice, but eating from 1-2-3 or 3-4-5 or 1-2 or 2-3-4-5 would be valid. Can you determine the number of different groups of shops Dhruv could have pastries from?
Input Format
The first line contains two space-separated integers N and K.
The next line contains N space-separated integers, representing the taste levels at each shop.
Output Format
Print the number of different groups of shops Dhruv could have pastries from.
Example
Input
3 3
1 2 3
Output
2
Constraints
1 <= N <= 10^5
|A_i| < 10^3
|K| < 10^7
Loading...
View Submissions
Console