## DMPG '15 G6 - Yōkan

View as PDF

Points: 25 (partial)
Time limit: 1.4s
Memory limit: 256M

Author:
Problem types

One day, Michiru and Makina found a great big Yōkan in Amane's room. This was no ordinary yōkan — it was rod-shaped and very long. Laid out horizontally, you can see that the yōkan is composed of segments, each segment one of different flavors (numbered from to ). Since the yōkan is so long, they may not be able to eat all of it. Therefore, they will choose a contiguous subsequence of the yōkan to eat. The girls will only eat pieces of one flavor because eating different flavors together will decrease the overall taste. If the length of the subsequence of the yōkan they choose to eat is , the girls both want to pick a flavor that has at least (real division, not integer division) pieces available for them to eat. They can pick the same flavor, but there must be enough pieces of that flavor for both of them to eat. Michiru and Makina have queries. Each query is in the form of — can the girls choose two (not necessarily different) flavors of yōkan that satisfies the above conditions if they only consider the sub-yōkan from to ?

Note: Michiru and Makina can eat fractional pieces.

#### Input Specification

The first line of input will have and .
The second line of input will have integers each between and (inclusive), the flavors of the pieces of yōkan, from left to right.
The third line of input will have , the number of queries.
The next lines each contain two integers and , the queries.

#### Output Specification

For each query, output a single line containing either YES (if the conditions can be satisfied) or NO (if the conditions can't be satisfied).

#### Sample Input

15 3
1 2 3 2 3 3 2 3 1 1 2 3 2 1 2
5
1 15
1 2
1 4
7 11
5 6

#### Sample Output

YES
YES
NO
YES
YES

#### Explanation of Output for Sample Input

In the first query, we can choose flavors and .
In the second query, we can choose flavors and .
In the third query, no matter which of single or pair of flavors we choose, there won't be enough for both Michiru and Makina.
In the fourth query, we can choose and .
In the fifth query, we can choose the single flavor , and give one to both Michiru and Makina (since they only require at least pieces each.

• commented on May 28, 2015, 1:18 p.m.

Is r-l+1=L?

• commented on May 28, 2015, 1:45 p.m.

Yes.

• commented on May 28, 2015, 12:14 p.m.

Can girls split piece in half between them?

• commented on May 28, 2015, 12:29 p.m. edited

Yes.

• commented on May 28, 2015, 12:06 p.m.

Can a girl eat 2.5 segments of a given flavour?

• commented on May 28, 2015, 12:29 p.m. edited

I stand corrected.

• commented on May 28, 2015, 1:23 p.m.

I can only get AC when I assume that you can split segments.

• commented on May 28, 2015, 1:27 p.m.

Thanks for the tip!