## Query In A Query

Points: 1
Time limit: 1.0s
Memory limit: 512M

Author:
Problem type

### 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$$

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

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$$