I have this problem and haven't solve it, yet. who has any idea, please give me :)

the problem is: give a sequence with n elements (n<=10^6), for example 4 3 2 1 and 2 number L,R (left and right)

count how many pair (i,j), i<=j that:

`L<=A[i]+A[i+1]+..+A[j]<=R`

someone will think this problem is easy, but the normal solution is O(n^2), and it will be run in long time. (limit is 3s). So, anyone else has some idea. I think this problem can solve in O(NlogN).

thnask ;)