Today HH is learning a new data structure named segment tree, which is often used to solve segment problem, here comes one:
Gave you an unordered sequence of length n,(a1,a2,…,an), now you are supposed to calculate how many segment [L,R](1≤L≤R) are there satisfies two conditions :
1.the length of the segment is k(i.e. R−L+1=k).
2.the number between L and R(both including) appears at least q times in total.
HH thinks the problem is too easy so he gives the problem to you.