ChefTown Parade

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=RL+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 nondecreasing order.
 Segment [L,R] is interesting if B[i]B[i1]=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.
Example
Input 1: 2 1 2 1 Input 2: 4 2 1 2 3 4 Output for Input 1: 2 Output for Input 2: 3
Author:  rubanenko 
Tester:  laycurse 
Editorial  http://discuss.codechef.com/problems/CHEFTOWN 
Tags  Rubanenko datastructure deque sep12 
Date Added:  3082012 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.4, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions