All submissions for this problem are available.
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.
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.
For each test case output a single integer - the number of interesting segments of buildings of length W.
Input 1: 2 1 2 1 Input 2: 4 2 1 2 3 4 Output for Input 1: 2 Output for Input 2: 3
|Tags||Rubanenko, data-structure, deque, sep12|
|Time Limit:||0.39645 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.