{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003cp\u003e \u003c/p\u003e\n\u003cp\u003eA sequence in which the value of elements first increase and then decrease is called Mountain- Sequence. In a valid Mountain-Sequence there should be at least one element in the increasing and at least one element in the decreasing arm.\u003cbr /\u003e\n\u003cbr /\u003e\u003cbr /\u003e\nFor example, \"1 3 5 9 17 12\" is a valid Mountain-Sequence 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 Mountain-Sequence since \"1 4 6\" has no element in the decreasing part while \"9 8 6\" has no element in the increasing part.\u003cbr /\u003e\n\u003cbr /\u003e\u003cbr /\u003e\nA sub-sequence 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 sub-sequences of \"8 2 7 10 6\" \u003c/p\u003e\n\u003cp\u003eGiven a sequence of N numbers finding its longest sub-sequence which is a Mountain-Sequence is the main problem here. The bigger problem is to find, how many such sequences exist. \u003cbr /\u003e\u003cbr /\u003e\nTo make it clearer, assume that the longest mountain-sequence 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.\n\u003c/p\u003e\n\u003cp\u003e \u003c/p\u003e\n\u003ch3\u003eInput\u003c/h3\u003e\n\u003cul\u003e\n\u003cli\u003eThe first line contains the no of test cases(T).\n\u003c/li\u003e\u003cli\u003eFirst line of each test case contains an integer \u003cb\u003eN\u003c/b\u003e , the number of element in the given sequnce.\u003c/li\u003e\n\u003cli\u003e\nThen follows N integers A1, A2.... An, Ai is ith element of the given sequence. These numbers will be newline separated.\n\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003e \u003c/p\u003e\n\u003ch3\u003eOutput\u003c/h3\u003e\n\u003cp\u003ePrint the NUMBER of longest-length Mountain Sequences in the given sequence.\u003cbr /\u003e\n\u003cbr /\u003e\u003cbr /\u003e\nNote:- A sequence with only one element is not a mountain-Sequence and no two adjacent elements in a Mountain-Sequence 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 sub-sequences having element 7 ONLY.\u003cbr /\u003e\n.\u003c/p\u003e\n\u003cp\u003e \u003c/p\u003e\n\u003ch3\u003eConstraints\u003c/h3\u003e\n\u003cul\u003e\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eT\u003c/b\u003e ≤ \u003cb\u003e100\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eAi\u003c/b\u003e ≤ \u003cb\u003e10000\u003c/b\u003e\n\u003c/li\u003e\u003c/ul\u003e\n\u003cp\u003e \u003c/p\u003e\n\u003ch3\u003eExample\u003c/h3\u003e\n\u003cpre\u003e\u003cb\u003eInput:\u003c/b\u003e\n1\n12\n5 4 7 89 10 23 29 56 8 5 30 70\n\n\u003cb\u003eOutput:\u003c/b\u003e\n2\n\u003c/pre\u003e\u003cp\u003e \u003c/p\u003e\n\u003ch3\u003eExplanation\u003c/h3\u003e\n\u003cp\u003e\u003cb\u003eExample case 1.\u003c/b\u003e\u003cbr /\u003e\nThe longest Mountain Sequences have length 8. The mountain sequences in this sequence are:\u003cbr /\u003e\n\u003cbr /\u003e\u003c/p\u003e\n\u003cpre\u003e\n4 7 10 23 29 56 8 5\n5 7 10 23 29 56 8 5\n\u003c/pre\u003e\n"}}]}