### No.209 Longest Mountain Subsequence

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 64 MB / 通常問題
タグ : / 解いたユーザー数 51

ProblemId : 368 / 出題時の順位表

#### Statement

Find the maximum length of the subsequence $\{B_i\}_{i=1}^k$ of the given sequence $\{A_i\}_{i=1}^N$ such that
$\quad 1 \leq {}^\exists j \leq k, \;\; B_1 < B_2 < \cdots < B_j > \cdots > B_{k-1} > B_k \; \wedge \; |B_1-B_2| < |B_2-B_3| < \cdots < |B_{j-1}-B_j| \; \wedge \; |B_j - B_{j+1}| > |B_{j+1} - B_{j+2}| > \cdots > |B_{k-1}-B_k|$.

Fig. 1. The view from Nihondaira (Dec. 27th, 2014)

#### Input

The first line of the input contains an integer $T$, denoting the number of test cases.
Then $T$ test cases follow, and the format of each test case is as follows:
$N$
$A_1$ $A_2$ $\cdots$ $A_N$


$1 \leq T \leq 100$
$1 \leq N \leq 100$
$0 \leq A_k \leq 1000000000 = 10^9$
All variables are non-negative integers.

#### Output

For each test cases, print the maximum length of $B$.

#### Sample

###### Input
4
5
1 2 3 4 5
9
1 2 4 8 100 8 4 2 1
9
1 7 5 3 1 6 3 9 1
1
1

###### Output
3
9
5
1


In the first case, $B=1,2,4$ is one of the desired subsequence, and another is $B=1,2,5$.
In the second case, $B=A$ is a valid subsequence.
In the third case, $B=1,3,6,3,1$ has length $=5$.
In the fourth case, the sequence consisted of only one element is also valid.

だんだん大きくなって，だんだん小さくなる列で，最大値に近づくほど差が急になるものです．