5291: Arithmetic Progression
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
Le Le loves sequences, so El El gives him one as present days ago.
Le Le treasures the sequence aa, and everyday he will do the following as routine:
An arithmetic progression is a sequence a1,a2,⋯,an that ∀1<i<n,2ai=ai−1+ai+1.
- Choose a subsequence al,al+1⋯,ar, create a new sequence b, and let bi−l+1=ai(l≤i≤r)bi−l+1=ai(l≤i≤r).
- Sort b1,b2,⋯,br−l+1 increasingly.
For he takes arithmetic progressions as the most beautiful sequences in the world, he wonders how many ways to choose the subsequence so that b could be an arithmetic progression.
输入
The first line contains an integer T — number of test cases.
Each test case contains two lines:
The first line contains an integer nn, denoting the length of the sequence.
输出
Output T lines containing the number of possible subsequences for each test case.
样例输入 复制
1
6
1 4 3 2 5 7样例输出 复制
15提示
T≤4.
For each test case, it's guaranteed that 1≤n≤105,1≤ai≤109 and all ai are distinct.