问题描述
六年级的暑假，在腾讯实习的xiaoxin巨从leader那得到了很多西瓜糖。每个西瓜糖都有一个属性代表它的甜度值，用一个正整数表示。
xiaoxin从小就特别会玩，他先把所有糖果排成一条直线，每次从一个区间内选出三个连续的且甜度值不减的西瓜糖来吃，即：
如果他选择了三元组 $(a_i, a_j, a_k)$ 那么:
1. $j = i + 1, k = j + 1$
2. $a_i \leq a_j \leq a_k$
好奇的xiaoxin想知道每次吃糖果，他有多少种吃法？
我们认为两个三元组 $(a_0, a_1, a_2), (b_0, b_1, b_2)$ 是不同的，当且仅当：
$a_0 \neq b_0$ or $a_1 \neq b_1$ or $a_2 \neq b_2$.
输入描述
多组测试数据， 第一行为一个整数($T \leq 10$)表示测试数据组数。
对于每组测试数据，第一行是一个整数 $n(1 \leq n \leq 200,000)$ 表示西瓜糖的个数。接下来 $n$个数表示每个西瓜糖的甜度值（$0 \leq a_i \leq 1000,000,000$）。接下来有 $Q(1 \leq 200,000)$ 行代表询问的次数，每个询问用两个整数 $l, r(1\leq l \leq r \leq n)$ 表示。
输出描述
对于每次询问，输出一个数，表示这次xiaoxin的吃法的数目。
输入样例
1
5
1 2 3 4 5
3
1 3
1 4
1 5
输出样例
1
2
3
