Intervals and subarrays

All submissions for this problem are available.
Read problems statements in Mandarin Chinese , Russian and Vietnamese
Chef Rahul likes those arrays that can be rearranged to form an interval of values  an increasing sequence where each element is greater than the previous by exactly one. For example:
 Rahul likes the array [3, 6, 5, 4] as it can be rearranged to [3, 4, 5, 6].
 Rahul doesn't like [1, 2, 4, 5] as no clear interval can be defined from these elements.
Given an array a of length n, your task is to write a program that counts the number of contiguous subarrays of a liked by Rahul that have length not less than w.
Input:
The first line contains a single integer T, the number of test cases to follow. Each of the test cases contain exactly 2 lines.
The first line contains two spaceseparated integers n and w.
The next line contains exactly n spaceseparated integers, denoting the array a.
Output:
You should output exactly T lines each containing answer for corresponding test case.
Constraints:
 1 ≤ T ≤ 10^{5}
 1 ≤ n ≤ 10^{6}
 sum of n over all testcases does not exceed 10^{6}
 1 ≤ w ≤ n
 a is a permutation of values [1, 2, 3 ... n]
Example
Input:
2 3 1 2 3 1 6 3 6 1 5 3 4 2
Output:
5 5
Explanation
Example case #1:
The following 5 subarrays form an interval:
 [2]
 [3]
 [1]
 [2, 3]
 [2, 3, 1]
Example case #2:
The following 5 subarrays form an interval:
 [6, 1, 5, 3, 4, 2] forms [1..6]
 [1, 5, 3, 4, 2] forms [1..5]
 [5, 3, 4] forms [3..5]
 [5, 3, 4, 2] forms [2..5]
 [3, 4, 2] forms [2..4]
Note that [3, 4] also forms an interval but cannot be counted as its length is less than w(= 3).
Author:  code_master01 
Editorial  http://discuss.codechef.com/problems/ANKINTER 
Tags  code_master01, snck151c 
Date Added:  1062015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, 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, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 