ChefTown is the biggest city and the capital of ChefLand. There are N beautiful buildings: restaurants, museums, living houses with large kitchens and so on. Every building has its height. For every i (1≤i≤N) there is exactly one building with height i. The buildings are located in a single line from left to right. The height of ith building is H(i). The Mayor of ChefTown wants to organize a parade, where all great chefs will take part. A parade depends of its location. The location of a parade is a segment of consecutive buildings beginning near the building number L and ending near the building number R (1≤L≤R≤N). Any parade won't be interesting if it is not hold on an interesting segment of buildings. The segment of buildings is interesting if following are hold:

Imagine, that we have a segment [L,R].
Let K=R-L+1 be the length of this segment, and B be a list of heights of the buildings that belong to this segment.
Let's sort B in non-decreasing order.
Segment [L,R] is interesting if B[i]-B[i-1]=1 for every i (2≤i≤K).

Now the Mayor of ChefTown is interested how many ways to organize an interesting parade of length W for ChefTown citizens. Help him and find out the number of different parades of length W, which can be hold in the city. Two parades ([L1,R1] and [L2,R2]) are considered to be different, if L1≠L2 or R1≠R2.

------ Input ------

Each input file consists of two lines, the first one contains two integers N and W (1≤N≤400000, 1≤W≤N). The second line contains N numbers H(i) (1≤i≤N) - the heights of the buildings.

------ Output ------

For each test case output a single integer - the number of interesting segments of buildings of length W.

----- Sample Input 1 ------
2 1
2 1
----- Sample Output 1 ------
2
----- explanation 1 ------

----- Sample Input 2 ------
4 2
1 2 3 4
----- Sample Output 2 ------
3
----- explanation 2 ------

见题面

见题面