#描述#
If a sequence{ b1, b2, b3,…, bn } satisfies ( b1 <= b2 <= b3 <= … <= bn ),then we can call it non-decreasing sequence. To this problem, you are given n integers { a[1], a[2], a[3], … , a[n] }. In addition to that, you are given Q queries, each queries is made up with two integers x and y (1 <= x <=y <= n). For each query, your task is to find the length of the longest non-decreasing subsequence of the sequence of { a[x],a[x+1],a[x+2],… ,a[y] }.We also can consider that to find the longest non-decreasing is to find the max result of e-s+1 while s and e satisfies ( x<=s<=e<=y && a[s]<=a[s+1]<=a[s+2]<=…<=a[e] ). Let maxlen1 be the answer query 1, maxlen2 be the answer of query 2.Your task is to calculate the sum of all the queries’ answer: maxlen1 + maxlen2 + … + maxlenQ.

#格式#
##输入格式##
The first line of the input file contains a integer of the case number T(1&lt=T&lt=10). For each case, line one: N,(1&lt=N&lt=10000) the length of the sequence. Then followed N integers: a[1], a[2], a[3], … , a[n].
The next line is a integer of queries number Q, (1&lt=Q&lt=10000). Q lines Following, each line contains two integers x, y (1&lt=x&lt=y&lt=n)

##输出格式##
For each query , calculate the length of the longest non-decreasing sequence. For each case output the sum of all queries’ answer: maxlen1 + maxlen2 + … + maxlenQ.

#样例1#
##样例输入1##

2
3
1 8 7
2
1 2
3 3
5
1 4 3 5 5
7
1 2
1 3
1 4
1 5
2 3
2 4
2 5

##样例输出1##

3
15

#限制#
1000ms
32768KB

#提示#
Case 1:
query 1: 1 2 means the sequence of {1,8}.
Obviously,the longest non-decreasing subsequence of it is {1,8}. maxlen = 2
query 2: 3 3 means the sequence of {7}.
The longest non-decreasing subsequence of it is {7},maxlen = 1;
Therefore,the answer of case 1 is 2 + 1 = 3;
Case 2:
query 1: 1 2 means {1,4} maxlen = 2;
query 2: 1 3 means {1,4,3} maxlen = 2;

query 3: 1 4 means {1,4,3,5} maxlen = 2;
query 4: 1 5 means {1,4,3,5,5} maxlen = 3;
query 5: 2 3 means {4,3} maxlen = 1;
query 6: 2 4 means {4,3,5} maxlen = 2;
query 7: 2 5 means {4,3,5,5} maxlen = 3;
So the answer of case 2 is 2 + 2 + 2 + 3 + 1 + 2 + 3 = 15;

#来源#
moonlight