Problem C: Cute Tree

上一题 正确率: $44.44\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $128$ 兆字节/Megabyte(s)
提交总数 $9$ 正确数量 $4$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 树

Description

Given the pseudo-code of a function Build−Tree(A,id,L,R):


where A is given in input, id is the number of node, L ,R is the left position and the right position of A

Require the number of nodes created by Build−Tree(A,root,1,n).

Input

The first line contains an integer T (1≤T≤5) representing the number of test cases.

For each test case, the first contain one integer n(1≤n≤2∗105).

The second line contain n integers Ai(1≤ Ai ≤109).

Output

For each test output one line, the number of nodes created by Build−Tree(A,root,1,n).

Sample Input复制

2
4
2 2 5 3
10
21 10 5 89 12 3 42 13 55 76

Sample Output复制

6
15