CDGLF4 - Majority Party

Majority Party

There are n houses in a locality. Every house gives a vote to a single party(say, AAP).(Party is denoted by a number). You are given queries (l to r) and asked to find if there exists a majority party in houses numbered from l to r.

Note:A party is considered in majority if there exists a subarray of size > (size of range)/2 in which all votes are of the same party.(In case of odd , consider floor function).

Input

First line contains number n , the number of houses in the locality.

Second line contains the n numbers denoting the party number of the vote of the ith house.

Third line contains M which is the number of queries.

M lines are given of the form l r.

 

Output

 

Output M lines containing the answer for each query in a single line.

Answer of each query is of form "yes" or "no".

 

Constraints

 

n<=10^5

a[i]<=10^8

m<=10^5

1<=l<=r<=n

 

Sample Input

 

5

2 2 2 3 3

2

2 5

2 4

 

Sample Output

 

no

yes


 


Added by:CSI
Date:2015-02-12
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY

hide comments
2015-02-15 05:38:18 Mitch Schwartz
Hmm, the whole time while solving I interpreted "subarray" as a synonym of subsequence (which seems most natural in the context of the problem), but now I'm thinking maybe it has to be a contiguous subsequence. Please clarify.

Update: After AC, I can confirm that subarray = contiguous subsequence.

Incidentally, the question as I originally (mis)understood it is also very interesting, and good for golfing too. :)

Edit: The other interpretation exists as classical version: PATULJCI.

Last edit: 2015-02-15 08:19:42
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.