No.209 Longest Mountain Subsequence
LayCurseStatement
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.
補足：$\exists$ は存在するという意味，$\wedge$ は「かつ（and）」を意味します．
だんだん大きくなって，だんだん小さくなる列で，最大値に近づくほど差が急になるものです．
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。