GTY's gay friends

GTY has $ n $ gay friends. To manage them conveniently, every morning he ordered all his gay friends to stand in a line. Every gay friend has a characteristic value $ a_i $ , to express how manly or how girlish he is. You, as GTY's assistant, have to answer GTY's queries. In each of GTY's queries, GTY will give you a range $ [l, r] $ . Because of GTY's strange hobbies, he wants there is a permutation $ [1..r-l+1] $ in $ [l, r] $. You need to let him know if there is such a permutation or not.

Multi test cases (about 3) . The first line contains two integers n and m ( $ 1 \leq n, m \leq 1000000 $ ), indicating the number of GTY's gay friends and the number of GTY's queries. the second line contains n numbers seperated by spaces. The $i^{th}$ number $a_i$ ( $ 1 \leq a_i \leq n $ ) indicates GTY's $i^{th}$ gay friend's characteristic value. The next m lines describe GTY's queries. In each line there are two numbers l and r seperated by spaces ( $ 1 \leq l \leq r \leq n $ ), indicating the query range.

For each query, if there is a permutation $ [1..r-l+1] $ in $ [l, r] $, print 'YES', else print 'NO'.

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

YES
NO
YES
YES
YES
YES
NO

BestCoder Round #29