After Iran-Egypt relations improved, three Iranians were able to obtain Egyptian visas. After arriving in Egypt, they plan to visit the famous street "Talaat Harb" first. on this street
n
There are n buildings that are in a straight line and in order from left to right from
1
1 to
n
n are numbered. The beauty of the building
i
i is equal to
a
i
a
i
​
 is

Now at the airport
Q
Q Taxi available. Taxi no
i
I picked up those three people at the airport and in front of the building
l
i
l
i
​
 He gets off and then in front of the building
r
i
r
i
​
 He waits to pick them up and take them to the hotel.
(
l
i
≤
r
i
)
(l
i
​
 ≤r
i
​
 ) they if taxi no
i
choose i, after getting off the taxi, they always go to the right to the building
r
i
r
i
​
 arrive and take a taxi there.

They plan to visit a number of (at least one) buildings so that the visited buildings are consecutive. Note that in normal mode they only pass in front of the building and do not necessarily visit every building they pass in front of.

The first person is satisfied with seeing a building if its beauty is definitely more than all the previous buildings visited.
The second person is also satisfied with seeing a building if the beauty of that building is strictly less than all the buildings they visit.
The third person, because he is older than the other two, does not have a strange taste and is satisfied with seeing all the buildings.
It is pleasant for them to visit a building if the majority of them (at least two people) are satisfied to visit that building.

For each taxi, they want to know how many ways they can select and visit a number of buildings they pass. Note that they are from the buildings
l
i
l
i
​
 and
r
i
r
i
​
 They can also visit. In other words, they are from the buildings of a subinterval of the interval
[
l
i
,
r
i
]
[l
i
​
 R
i
​
 ] are visiting.

Also, the third person, as the oldest person in the group, advises you to pay attention to the sample entries for a better understanding of the question.

input
In the first line of input,
n
n or the same number of buildings comes.
1
≤
n
≤
500
,
000
1≤n≤500,000

In the second input line,
n
n integers come that number
i
I am the same
a
i
a
i
​
 is
0
≤
a
i
≤
1
0
9
0≤a
i
​
 ≤10
9


In the third line of input,
Q
Q or the same number of taxis comes.
1
≤
Q
≤
500
,
000
1≤Q≤500,000

in
Q
Q next line in each line two numbers
r
i
r
i
​
 and
l
i
l
i
​
 They come in order.
1
≤
l
i
≤
r
i
≤
n
1≤l
i
​
 ≤r
i
​
 ≤n

output
In the only output line
Q
Q number print that number
i
The i th number of modes of visiting them if using a taxi
i
is i

Sub-issues
Constraint score subproblem
1 9
n
≤
500
n≤500
2 16
n
≤
5000
n≤5000
3 36
n
≤
1
0
5
,
Q
≤
3000
n≤10
5
 , Q ≤ 3000
4 39 without additional restrictions
examples
Sample entry 1
5
5 4 1 3 2
5
1 5
2 5
2 4
1 3
1 2
Plain text
Sample output 1
11 9 6 5 3
Plain text
Sample entry 2
9
5 2 3 3 6 4 6 4 1
5
19
4 9
3 8
2 5
7 8
Plain text
Sample output 2
29 15 18 10 3
Plain text
At the input of the first example, for the second taxi, the total number of modes that can visit a number of consecutive buildings is equal to
10
is 10 Out of this
10
10 states, the state of the entire building range
[
2
,
5
]
[2,5] It is not pleasant for them to visit; Because the first and second people are satisfied to visit the building with beauty
3
3 are notc++