Mountain Holidays 2

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Let’s remember the problem Mountain holidays (MOU1H). The story of Mountain holidays is the following. Some time ago, Chef discovered that more and more people have started climbing mountains every day. So he decided to build a restaurant in the Ukrainian resort Bukovel (Carpathian Mountains). But there are many places to choose, so he wants to choose the best one.
By your great helps, Chef could find to the best place to build a restaurant, now Chef becomes rich. Now he wants to build a restaurant in the next mountain. Similar to previous one, the next mountain is described by a sequence of N points. Here the points are numbered from 1 to N, and the height of point k is denoted by H_{k}. Every two adjacent points of the mountain are connected by a segment.
For example, the mountain described by N = 9, H = [0, 2, 1, 2, 1, 3, 0, 1, 0] is like a following:
/\ /\/\/ \ / \/\
In the mountain, all of the tourists will go from the point 1 to point N.
For comfort of the tourists, Chef has bought teleports too. Using a teleport, a tourist can be transferred from point i to point j, for all i < j. Of course, tourists can also walk from point i to point i+1 on foot.
Now Chef wants to calculate the attractiveness of the mountain, as the number of the different climbs.
A climb is defined by the nonempty sequence (p_{1}, p_{1}+1), (p_{2}, p_{2}+1), ..., (p_{s}, p_{s}+1) of the moves on foot , where p_{k}+1 ≤ p_{k+1} for k = 1, 2, ..., s − 1.
Two climbs, say (p_{1}, p_{1}+1), (p_{2}, p_{2}+1), ..., (p_{s}, p_{s}+1) and (q_{1}, q_{1}+1), (q_{2}, q_{2}+1), ..., (q_{t}, q_{t}+1) are different if and only if s ≠ t or
 There exists at least one k such that 1 ≤ k < min(s, t) and H_{pk+1} – H_{pk} ≠ H_{qk+1} – H_{qk}.
You are given the array H, find the number of the different climbs that exist on the mountain. Since the answer can be very large, output it modulo 10^{9}+9 = 1000000009.
Input
The first line of input contains T, denoting the number of test cases. Then T test cases follow.
The first line of each test case contains an integer N, denoting the number of points on the mountain. On second line of each test case, there are N spaceseparated integers H_{1}, H_{2}, ..., H_{N}, denoting the height of each point.
Output
For each test case, output an integer denoting the number of the different climbs modulo 10^{9}+9 = 1000000009.
Constraints
 1 ≤ T ≤ 100000, that is, 1 ≤ T ≤ 10^{5}
 2 ≤ N ≤ 1000000, that is, 2 ≤ N ≤ 10^{6}
 Sum of N over all test cases in one file will be at most 1000000 = 10^{6}
 2000000 ≤ H_{k} ≤ 2000000, that is, −2 × 10^{6} ≤ H_{k} ≤ 2 × 10^{6}
Sample
Input 3 6 1 2 3 4 5 6 9 0 2 1 2 1 3 0 1 0 7 0 5 5 5 5 4 4 Output 5 199 55
Explanation
In the first test case, since height increases by one for each move on foot, there will be one unique climb for each length. So there are 5 climbs with length 1, 2, ..., 5. Here length means the number of moves by foot.
We can get the following 5 distinct climbs.
 (1, 2)
 (1, 2), (2, 3)
 (1, 2), (2, 3), (3, 4)
 (1, 2), (2, 3), (3, 4), (4, 5)
 (1, 2), (2, 3), (3, 4), (4, 5), (5, 6)
The second test case is taken from the problem statement.
Warning: The input and output can be large. Please don't use a slow input/output method.
Author:  witalij_hq 
Editorial  http://discuss.codechef.com/problems/MOU2H 
Tags  aug14, dynamicprogramming, medium, witalij_hq 
Date Added:  30032013 
Time Limit:  0.5 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, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions