In this HackerEarth Update And Query problem, Deepankar loves to play with the arrays a lot. Today, he has an array A of N integers. He has to fulfill M operations. Each operation has one of the following two types:

U X Y : Update the value at the Xth index of the array with Y.

Q X C : Calculate the length of the longest subarray that starts at Xth index and satisfy following inequality

A[X]-C ≤ V ≤ A[X] + C
Where V is any value from the chosen subarray.
Deepankar is facing difficulty in maintaining the efficiency of the operations. Can you help him in accomplishing this task efficiently.

## HackerEarth Update And Query problem solution.

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

#define MAXN 100001
#define ft first
#define sd second

int N,M,A[MAXN],STMX[4*MAXN],STMN[4*MAXN],X,Y,C;
char str ;

void buildst(int idx,int ss,int se){

if(ss == se){
STMX[idx] = A[ss] ;
STMN[idx] = A[ss] ;
return ;
}
int mid = (ss + se)/2;
buildst(2*idx,ss,mid) ;
buildst(2*idx+1,mid+1,se) ;
STMX[idx] = max(STMX[2*idx],STMX[2*idx+1]) ;
STMN[idx] = min(STMN[2*idx],STMN[2*idx+1]) ;
}

void update(int idx,int ss,int se,int val,int pos){

if(ss == se){
STMX[idx] = val ;
STMN[idx] = val ;
return ;
}

int mid = (ss + se)/2 ;
if(pos <= mid)
update(2*idx,ss,mid,val,pos) ;
else
update(2*idx+1,mid+1,se,val,pos) ;

STMX[idx] = max(STMX[2*idx],STMX[2*idx+1]) ;
STMN[idx] = min(STMN[2*idx],STMN[2*idx+1]) ;
}

pair<int,int> query(int idx,int ss,int se,int l,int r){

pair<int,int> ret ;
if(l > se || r < ss){
ret.ft = INT_MIN ;
ret.sd = INT_MAX ;
return ret ;
}
if(l <= ss && se <= r){
return make_pair(STMX[idx],STMN[idx]) ;
}
int mid = (ss + se)/2 ;
pair<int,int> left ,right ;
left  = query(2*idx,ss,mid,l,r) ;
right = query(2*idx+1,mid+1,se,l,r) ;
return make_pair(max(left.ft,right.ft),min(left.sd,right.sd)) ;
}

bool check(int L,int R,int C){
pair<int,int> ret ;
ret = query(1,1,N,L,R) ;
return ((ret.ft-A[L] <= C) && (A[L]-ret.sd <= C)) ;
}

void solve(int X,int C){

int V1,V2 ;
V1 = V2 = -1 ;

if(C >= 0){
int low , high , mid ;
low = X ;
high = N ;
while(low <= high){
mid = (low + high)/2 ;
bool f = check(X,mid,C) ;
if( f && (mid == N || check(X,mid+1,C) == 0)){
break ;
}else if(f){
low = mid+1 ;
}else{
high = mid-1 ;
}
}
V1 = mid-X+1 ;
pair<int,int> ret = query(1,1,N,X,mid) ;
V2 = max(ret.ft-A[X],A[X]-ret.sd) ;
}
printf("%d %d\n",V1,V2) ;
}
int main(){

scanf("%d%d",&N,&M) ;
assert(N >= 1 && N <= 100000) ;
assert(M >= 1 && M <= 200000) ;
for(int i=1;i<=N;i++){
scanf("%d",&A[i]) ;
assert(A[i] >= 1 && A[i] <= 1000000000) ;
}
buildst(1,1,N) ;
while(M--){
scanf("%s",str+1) ;
if(str == 'U'){
scanf("%d%d",&X,&Y) ;
A[X] = Y ;
update(1,1,N,Y,X) ;

}else if(str == 'Q'){
scanf("%d%d",&X,&C) ;
solve(X,C) ;
}else{
assert(0) ;
}
}
return 0 ;
}```