Mountain Engineering

A sequence in which the value of elements first increase and then decrease is called Mountain Sequence. In a valid MountainSequence there should be at least one element in the increasing and at least one element in the decreasing arm.
For example, "1 3 5 9 17 12" is a valid MountainSequence having five elements in the increasing arm namely 1, 3, 5, 9 and 17, and 1 element in the decreasing arm namely 12 . But none of the sequence "1 4 6" or "9 8 6" are MountainSequence since "1 4 6" has no element in the decreasing part while "9 8 6" has no element in the increasing part.
A subsequence of a sequence is obtained by deleting zero or more elements from the sequence. For example definition "7", "2 10", "8 2 7 6", "8 2 7 10 6" etc are valid subsequences of "8 2 7 10 6"
Given a sequence of N numbers finding its longest subsequence which is a MountainSequence is the main problem here. The bigger problem is to find, how many such sequences exist.
To make it clearer, assume that the longest mountainsequence in a given sequence is of length l. Then you have to find all subsequences which are mountain sequences of length l. Hence, you have to find NUMBER of these maximum length Mountain Sequences that can be extracted from the given sequence.
Input
 The first line contains the no of test cases(T).
 First line of each test case contains an integer N , the number of element in the given sequnce.
 Then follows N integers A1, A2.... An, Ai is ith element of the given sequence. These numbers will be newline separated.
Output
Print the NUMBER of longestlength Mountain Sequences in the given sequence.
Note: A sequence with only one element is not a mountainSequence and no two adjacent elements in a MountainSequence are of same value. Assume that two different elements of a sequence, which have the same value, represent different entities. E.g., if a sequence contains the element 7 at two places, then you have to consider two different subsequences having element 7 ONLY.
.
Constraints
 1 ≤ T ≤ 100
 1 ≤ Ai ≤ 10000
Example
Input: 1 12 5 4 7 89 10 23 29 56 8 5 30 70 Output: 2
Explanation
Example case 1.
The longest Mountain Sequences have length 8. The mountain sequences in this sequence are:
4 7 10 23 29 56 8 5 5 7 10 23 29 56 8 5
Author:  gothicprakhar 
Tags  gothicprakhar 
Date Added:  29042014 
Time Limit:  3 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