Today it’s the time for boogeyman to scare some children. Today he is visiting a street with n houses.Each house has 1 child and let a[i] denote the power boogeyman will get after scaring child in ith house. After scaring a child boogeyman gets some power, but this boogeyman has his own constraints, he will go to scare a child in a house if and only if he will get strictly more power than from the child in previously visited house.

Now boogeyman is asking for your help to know the maximum number of houses he can visit in a range [l,r] where l and r are the indices of a house on the street.

Constraints:

1<=n<=6000, where n is number of houses on the street.

1<=a[i]<=10^9, where a[i] is the amount of power boogeyman will get after visiting ith house.

1<=Q<=1000000, where Q is the number of queries in form l to r that you have to answer.

1<=l,r<=6000

Input:

First line of input will contain an integer n denoting number of houses on the street.

Next line of input contains n integers denoting the power boogeyman can get from ith house.

Next line contains an integer Q denoting number of queries followed by q lines each having 2 integers l and r denoting the range of house in which boogeyman wants his answer.

Output:

Output for each query the maximum number of houses boogeyman can visit.