Query In A Query

Alden some permutation \(a\) of the numbers \(1\) to \(n\). He's very familiar with some properties of this permutation, to the extent that simple range queries are a trivial problem to him. However, he ponders the idea of a range query containing a similar query. Alden thinks to himself, if he defined a function \(g\) such that \(g(l, r)\) gives the index of the maximum in \(a\) in the range \(l\) to \(r\), and then defines another function \(f\) such that \(f(l, r) = r - l + 1 + f(l, g(l, r) - 1) + f(g(l, r) + 1, r)\) if \(l <= r\) or \(0\) otherwise that this would make an interesting problem. Help to cure Alden's curiosity.

Input Specification

The first line contains one integer \(n\) The next line contains \(n\) space seperated integers \(a_i\) for \(1\leq{i}\leq{n}\) The next lie contains one integer \(q\) The next \(q\) lines contain 2 space seperated integers \(l_j\) and \(r_j\) for \(1\leq{j}\leq{n}\)

Output Specification

print \(q\) integers, each on a new line where each integer is the result of \(f(l_j, r_j)\)

Bounds

\(2 \leq n \leq 10^5\)
\(1 \leq q \leq 10^5\)
\(l_j \leq r_j\)

Sample Input

4
3 1 4 2
5
2 2
1 3
1 4
2 4
1 1

Sample Output

1
6
8
5
1

Explanation

\(f(2, 2) = 2 - 2 + 1 + f(2, 1) + f(3, 2) = 1 + 0 + 0 = 1\)
\(f(1, 3) = 3 - 1 + 1 + f(1, 2) + f(4, 3) = 3 + (2 - 1 + 1 + f(1, 0) + f(2, 2)) + 0 = 3 + 2 + 0 + 1 = 6\)
\(f(1, 4) = 4 - 1 + 1 + f(1, 2) + f(4, 4) = 4 + 3 + (4 - 4 + 1 + f(4, 3) + f(5, 4)) = 4 + 3 + 1 = 8\)
\(f(2, 4) = (4 - 2 + 1) + f(2, 2) + f(4, 4) = 3 + (2-2+1 + 0 + 0) + (4-4 + 1 + 0 + 0) = 5\)
\(f(1, 1) = (1 - 1 + 1) + 0 + 0 = 1\)