GTY has nn 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 aiai , 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][l,r] . Because of GTY's strange hobbies, he wants there is a permutation [1..r−l+1][1..r−l+1] in [l,r][l,r]. You need to let him know if there is such a permutation or not.

Input

Multi test cases (about 3) . The first line contains two integers n and m ( 1≤n,m≤10000001≤n,m≤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 ithith number aiai ( 1≤ai≤n1≤ai≤n ) indicates GTY's ithith 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≤l≤r≤n1≤l≤r≤n ), indicating the query range.

Output

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

Sample Input

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

Sample Output

YES
NO
YES
YES
YES
YES
NO

题意：

问区间[l,r]内的元素是否可以构成从1到r-l+1的一个排列。

思路：

如果可以构成，则[l,r]的区间和一定等于（r-l+1）*（r-l+2）/2

先判断区间和，符合条件的再判断区间内有无重复元素

预处理出每个数字上一次出现的位置，存入pre中，由于数据较大，所以建线段树来查找[l,r]中pre的最大值，若该值<l，说明[l,r]中没有重复元素，符合条件。

具体实现见代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
typedef long long ll;
const int N=1e6+3;

int n,m;
int pre[N],now[N];///pre[i]第i个数字上一次出现的位置（下标） now[i]当前数字的位置(qwq亲测用map会爆内存)
ll a[N];///前缀和
int cnt;

struct node
{
    int l,r,sum;///刚开始直接拿了板子抄过来，没有去掉siz（区间长度），结果爆内存了qwq
}T[4*N+1];

void update(int k)///更新区间最值
{
    T[k].sum=max(T[k*2].sum,T[k*2+1].sum);
}

void build(int k,int ll,int rr)///建树
{
    T[k].l=ll;
    T[k].r=rr;
    if(ll==rr)
    {
        T[k].sum=pre[++cnt];
        return ;
    }
    int mid=(ll+rr)/2;
    build(k*2,ll,mid);
    build(k*2+1,mid+1,rr);
    update(k);
}

int ask_sum(int k,int ll,int rr)///查询区间最值
{
    int ans=0;
    if(ll<=T[k].l&&T[k].r<=rr)
    {
        ans=max(ans,T[k].sum);
        return ans;
    }
    int mid=(T[k].l+T[k].r)/2;
    if(ll<=mid)
        ans=max(ans,ask_sum(k*2,ll,rr));
    if(rr>mid)
        ans=max(ans,ask_sum(k*2+1,ll,rr));
    return ans;
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        memset(a,0,sizeof(a));
        memset(pre,0,sizeof(pre));
        memset(T,0,sizeof(T));
        memset(now,0,sizeof(now));
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
            pre[i]=now[a[i]];
            now[a[i]]=i;
            a[i]=a[i-1]+a[i];
        }
        cnt=0;
        build(1,1,n);
        int l,r;
        while(m--)
        {
            scanf("%d%d",&l,&r);
            bool flag=0;
            int len=r-l+1;
            if(a[r]-a[l-1]==len*(len+1)/2)
            {
                int tmp=ask_sum(1,l,r);
                if(tmp<l)
                    flag=1;
            }
            if(flag)
                cout<<"YES"<<'\n';
            else
                cout<<"NO"<<'\n';
        }
    }
    return 0;
}