Not Equal on a Segment

C. Not Equal on a Segment

You are given array a with n integers and m queries. The i-th query is given with three integers li, ri, xi.

For the i-th query find any position pi (li ≤ pi ≤ ri) so that api ≠ xi.

Input

The first line contains two integers n, m (1 ≤ n, m ≤ 2·105) — the number of elements in a and the number of queries.

The second line contains n integers ai (1 ≤ ai ≤ 106) — the elements of the array a.

Each of the next m lines contains three integers li, ri, xi (1 ≤ li ≤ ri ≤ n, 1 ≤ xi ≤ 106) — the parameters of the i-th query.

Output

Print m lines. On the i-th line print integer pi — the position of any number not equal to xi in segment [li, ri] or the value  - 1 if there is no such number.

Sample test(s)

input

6 4
1 2 1 1 3 5
1 4 1
2 6 2
3 4 1
3 4 2

output

2
6
-1
4

-----------------------------------------------------editorial-------------------------------------------------------

initially i solved this problem using segment tree,  first i create a  min seg tree and a max seg tree,

now for range l , r    find min_index and max_index in the range l to r , min_index means index at which value is min in  l to r , similarly for the max_index ..

now 

case 1 if(va[min_index]== val[max_iondex]==x) ans is -1;

else if(val[min_index]!=x) ans=min_index;

else ans=max_index...

----------------------------------------------------but----------------------------------------------------------------

there is a easy solution of this problem also 

keep track of no of distinct nos in l to r 

 while reading input if arr[i]==arr[i-1]   than p[i]= p[i-1]

else p[i]=p[i-1]+1;

now for the calculation of the answer 

if(arr[L]!=x ) ans=L;

else find upper_bound of p[l]+1, if it is within r than ans = upper_bound(p.begin(),p.end(),p[l]+1)

//  since if there is a increasement ov value of p in the range of l+1, r than ans must be the increasing point index

else ans=-1;

/// here i am posting both answer seg tree , and implementation 

------------------------------------------code- -----segtree------------------------------------------------------------------------

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

int mini,maxi,mini_index,maxi_index;

#include<iostream>

using namespace std;

int arr[1010000];

int tree1[1010000],tree2[1010000];

void query1(int node,int start,int end,int r1,int r2)

 {

 

  

 if(start>end || r1>end || r2<start) return;

   if(r1<=start && r2>=end)

    {

  

     

     int mid=(start+end)/2;

     

       if(start==end  && mini>arr[start])

        {

        mini_index=start+1;

       

        mini=arr[start];

        return ;

}

     else if(tree1[2*node]<=tree1[2*node+1]  && start !=end)

      {

      query1(2*node,start,mid,r1,r2);

 }

 else if(start!=end)

 {

  query1(2*node+1,mid+1,end,r1,r2);

 }

 

     

    }

    

    else

    {

     query1(2*node,start,(start+end)/2,r1,r2);

    query1(2*node+1,((start+end)/2)+1,end,r1,r2);

    // return min(q1,q2);

    }

 }

 

 

 void query2(int node,int start,int end,int r1,int r2)

 {

 

 

  

 if(start>end || r1>end || r2<start) return ;

 

   if(r1<=start && r2>=end)

    {

     

     int mid=(start+end)/2;

       if(start==end  && maxi<arr[start])

        {

        maxi_index=start+1;

        maxi=arr[start];

        return ;

}

     else if(tree2[2*node]>=tree2[2*node+1]  && start!=end)

      {

      query2(2*node,start,mid,r1,r2);

 }

 else if(start!=end)

 {

  query2(2*node+1,mid+1,end,r1,r2);

 }

     

    }

    

    else

    {

       query2(2*node,start,(start+end)/2,r1,r2);

       query2(2*node+1,((start+end)/2)+1,end,r1,r2);

    

    }

 }

 

 void build2(int node , int start,int end)

 {

  if(start==end) tree2[node]=arr[start];

  else if(start>end) return ;

  else

   {

    build2(2*node,start,(start+end)/2);

    build2(2*node+1,((start+end)/2)+1,end);

    tree2[node]=max(tree2[2*node],tree2[2*node+1]);

   }

   

 }

 

 void build1(int node , int start,int end)

 {

  if(start==end) tree1[node]=arr[start];

  else if(start>end) return ;

  else

   {

    build1(2*node,start,(start+end)/2);

    build1(2*node+1,((start+end)/2)+1,end);

    tree1[node]=min(tree1[2*node],tree1[2*node+1]);

   }

   

 }

 

 

 

 

 

int main()

 {

 

   int n,m;

    cin>>n>>m;

    arr[0]=0;

   

   memset(tree1,10000000,sizeof(tree1));

     memset(tree2,-10000000,sizeof(tree2));

    for(int i=0;i<n;i++)

     {

     

      scanf("%d",&arr[i]);

  

     

}

build1(1,0,n-1);

build2(1,0,n-1);

 

 

for(int i=0;i<m;i++)

 {

     int l,r,x;

    scanf("%d %d %d",&l,&r,&x);

   mini_index=-1;

   maxi_index=-1;

   mini=10000000;

   maxi=-10000000;

   

     query1(1,0,n-1,l-1,r-1);

     query2(1,0,n-1,l-1,r-1);

     

    

     

     if(arr[mini_index-1]==x && arr[maxi_index-1]==x)

      printf("-1");

       else if(arr[mini_index-1]!=x)

           printf("%d",mini_index);

        else

        printf("%d",maxi_index);

        

        printf("\n");

 }

 }

---------------------------------------code---------------implementation ----------------------------------------

#include<bits/stdc++.h>
using namespace std;

vector<int> v,p;
int main()
 {
  int n,m;
   cin>>n>>m;
  
   p.push_back(0);
   v.push_back(INT_MAX);
   for(int i=1;i<=n;i++) 
   {
    int a;
     scanf("%d",&a);
    v.push_back(a);
     if(v[i]!=v[i-1])
     {
       p.push_back(p[i-1]+1);
     }
     else  p.push_back(p[i-1]);
   }
   for(int i=0;i<m;i++)
    {
      int l,r,x;
      scanf("%d %d %d",&l,&r,&x);
     //  cout<<v[l]<<" "<<v[r]<<endl;
       if(v[l]!=x)
       cout<<l<<endl;
       else
       {
         vector<int>:: iterator it;
         it=lower_bound(p.begin()+l,p.end(),p[l]+1);
         if(it==p.end() || it >p.begin()+r)
          cout<<"-1"<<endl;
          else cout<<it-p.begin()<<endl;
    }
    }
  
 }