No.209 Longest Mountain Subsequence

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

2 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.

補足:$\exists$ は存在するという意味,$\wedge$ は「かつ(and)」を意味します.
だんだん大きくなって,だんだん小さくなる列で,最大値に近づくほど差が急になるものです.

提出ページヘ