#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FAST_IO ios_base::sync_with_stdio(false), cin.tie(nullptr)
vector<multiset<ll>>tree;
vector<ll>arr;
ll pos,val,del,k,l1,r1;
ll getmax(ll a,ll b){
return a>b?a:b;
}
ll getmin(ll a,ll b){
return a<b?a:b;
}
void implement(int l,int r,int i){
if(l==r){
tree[i].insert(arr[l]);
return;
}
int m=(l+r)/2;
implement(l,m,i*2+1);
implement(m+1,r,i*2+2);
tree[i]=tree[i*2+1];
for(int f=m+1;f<=r;f++)tree[i].insert(arr[f]);
}
void update(int l,int r,int i){
if(l>pos||r<pos)return;
tree[i].insert(val);
tree[i].erase(del);
if(l==r){
return;
}
int m=(l+r)/2;
update(l,m,i*2+1);
update(m+1,r,i*2+2);
}
ll solve(int l,int r,int i){
if(l>r1||r<l1||(k>*(--tree[i].end())))return LLONG_MAX;
if(l>=l1&&r<=r1){
return *tree[i].lower_bound(k);
}
int m=(l+r)/2;
return getmin(solve(l,m,i*2+1),solve(m+1,r,i*2+2));
}
int brute_force()
{
ll answer = LLONG_MAX;
for (int i = l1; i <= r1; i++)
if (arr[i] >= k && answer > arr[i])
answer = arr[i];
return answer;
}
int main(){
FAST_IO;
ll s;
int n,m,t;
//cin>>n>>m;
n = 10;
m = 100;
arr.resize(n);
//for(auto &x:arr)cin>>x;
for(auto &x:arr) x = rand() % 20;
tree.resize(4*n+1);
implement(0,n-1,0);
while(m--){
//cin>>t;
t = rand() % 2;
if(t==1){
//cin>>pos>>val;
pos = rand() % n + 1;
val = rand() % 20;
pos--;
del=arr[pos];
update(0,n-1,0);
arr[pos]=val;
} else {
//cin>>l1>>r1>>k;
l1 = rand()%n + 1;
r1 = rand()%n + 1;
k = rand()%20;
l1--;
r1--;
s=solve(0,n-1,0);
if(s==LLONG_MAX)cout<<-1<<endl;
else cout<<s<<endl;
ll s2 = brute_force();
if(s2==LLONG_MAX)cout<<"Correct: " << -1<<endl<<endl;
else cout<<"Correct: " <<s2<<endl<<endl;
}
}
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdHlwZWRlZiBsb25nIGxvbmcgbGw7CiNkZWZpbmUgRkFTVF9JTyBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKSwgY2luLnRpZShudWxscHRyKQp2ZWN0b3I8bXVsdGlzZXQ8bGw+PnRyZWU7CnZlY3RvcjxsbD5hcnI7CmxsIHBvcyx2YWwsZGVsLGssbDEscjE7CgpsbCBnZXRtYXgobGwgYSxsbCBiKXsKICAgIHJldHVybiBhPmI/YTpiOwp9CgpsbCBnZXRtaW4obGwgYSxsbCBiKXsKICAgIHJldHVybiBhPGI/YTpiOwp9Cgp2b2lkIGltcGxlbWVudChpbnQgbCxpbnQgcixpbnQgaSl7CiAgICBpZihsPT1yKXsKICAgICAgICB0cmVlW2ldLmluc2VydChhcnJbbF0pOwogICAgICAgIHJldHVybjsKICAgIH0KICAgIGludCBtPShsK3IpLzI7CiAgICBpbXBsZW1lbnQobCxtLGkqMisxKTsKICAgIGltcGxlbWVudChtKzEscixpKjIrMik7CiAgICB0cmVlW2ldPXRyZWVbaSoyKzFdOwogICAgZm9yKGludCBmPW0rMTtmPD1yO2YrKyl0cmVlW2ldLmluc2VydChhcnJbZl0pOwp9Cgp2b2lkIHVwZGF0ZShpbnQgbCxpbnQgcixpbnQgaSl7CiAgICBpZihsPnBvc3x8cjxwb3MpcmV0dXJuOwogICAgdHJlZVtpXS5pbnNlcnQodmFsKTsKICAgIHRyZWVbaV0uZXJhc2UoZGVsKTsKICAgIGlmKGw9PXIpewogICAgICAgIHJldHVybjsKICAgIH0KICAgIGludCBtPShsK3IpLzI7CiAgICB1cGRhdGUobCxtLGkqMisxKTsKICAgIHVwZGF0ZShtKzEscixpKjIrMik7Cn0KCmxsIHNvbHZlKGludCBsLGludCByLGludCBpKXsKICAgIGlmKGw+cjF8fHI8bDF8fChrPiooLS10cmVlW2ldLmVuZCgpKSkpcmV0dXJuIExMT05HX01BWDsKICAgIGlmKGw+PWwxJiZyPD1yMSl7CiAgICAgICAgcmV0dXJuICp0cmVlW2ldLmxvd2VyX2JvdW5kKGspOwogICAgfQogICAgaW50IG09KGwrcikvMjsKICAgIHJldHVybiBnZXRtaW4oc29sdmUobCxtLGkqMisxKSxzb2x2ZShtKzEscixpKjIrMikpOwp9CgppbnQgYnJ1dGVfZm9yY2UoKQp7CiAgICBsbCBhbnN3ZXIgPSBMTE9OR19NQVg7CgogICAgZm9yIChpbnQgaSA9IGwxOyBpIDw9IHIxOyBpKyspCiAgICAgICAgaWYgKGFycltpXSA+PSBrICYmIGFuc3dlciA+IGFycltpXSkKICAgICAgICAgICAgYW5zd2VyID0gYXJyW2ldOwogICAgcmV0dXJuIGFuc3dlcjsKfQoKaW50IG1haW4oKXsKICAgIEZBU1RfSU87CiAgICBsbCBzOwogICAgaW50IG4sbSx0OwogICAgLy9jaW4+Pm4+Pm07CiAgICBuID0gMTA7CiAgICBtID0gMTAwOwogICAgYXJyLnJlc2l6ZShuKTsKICAgIC8vZm9yKGF1dG8gJng6YXJyKWNpbj4+eDsKICAgIGZvcihhdXRvICZ4OmFycikgeCA9IHJhbmQoKSAlIDIwOwogICAgdHJlZS5yZXNpemUoNCpuKzEpOwogICAgaW1wbGVtZW50KDAsbi0xLDApOwogICAgd2hpbGUobS0tKXsKICAgICAgICAvL2Npbj4+dDsKICAgICAgICB0ID0gcmFuZCgpICUgMjsKICAgICAgICBpZih0PT0xKXsKICAgICAgICAgICAgLy9jaW4+PnBvcz4+dmFsOwogICAgICAgICAgICBwb3MgPSByYW5kKCkgJSBuICsgMTsKICAgICAgICAgICAgdmFsID0gcmFuZCgpICUgMjA7CiAgICAgICAgICAgIHBvcy0tOwogICAgICAgICAgICBkZWw9YXJyW3Bvc107CiAgICAgICAgICAgIHVwZGF0ZSgwLG4tMSwwKTsKICAgICAgICAgICAgYXJyW3Bvc109dmFsOwogICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgIC8vY2luPj5sMT4+cjE+Pms7CiAgICAgICAgICAgIGwxID0gcmFuZCgpJW4gKyAxOwogICAgICAgICAgICByMSA9IHJhbmQoKSVuICsgMTsKICAgICAgICAgICAgayA9IHJhbmQoKSUyMDsKICAgICAgICAgICAgbDEtLTsKICAgICAgICAgICAgcjEtLTsKICAgICAgICAgICAgcz1zb2x2ZSgwLG4tMSwwKTsKICAgICAgICAgICAgaWYocz09TExPTkdfTUFYKWNvdXQ8PC0xPDxlbmRsOwogICAgICAgICAgICBlbHNlIGNvdXQ8PHM8PGVuZGw7CgogICAgICAgICAgICBsbCBzMiA9IGJydXRlX2ZvcmNlKCk7CiAgICAgICAgICAgIGlmKHMyPT1MTE9OR19NQVgpY291dDw8IkNvcnJlY3Q6ICIgPDwgLTE8PGVuZGw8PGVuZGw7CiAgICAgICAgICAgIGVsc2UgY291dDw8IkNvcnJlY3Q6ICIgPDxzMjw8ZW5kbDw8ZW5kbDsKICAgICAgICB9CiAgICB9Cn0=