## Query In A Query

### 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\)

## Comments