#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll l,r;
ll segtree[400001];
ll a[100001];
ll b[100001];
void build(ll node,ll b1,ll e)
{if(b1==e)
{
segtree[node]=b[b1];
cout<<b[b1]<<"\n";
}
else
{
ll mid=(b1+e)/2;
build(2*node,b1,mid);
build(2*node+1,mid+1,e);
l=segtree[2*node];
r=segtree[2*node+1];
if(a[l]<a[r])
{
segtree[node]=l;
}
else if(a[l]>a[r])
{
segtree[node]=r;
}
else if(a[l]==a[r])
{
segtree[node]=l;
}
else
{
}
}
}
ll sum1(ll node,ll b1,ll e,ll L,ll R)
{
if(b1>R || e<L)
{
return -1;
}
if (b1>=L && e<=R)
{
return segtree[node];
}
ll mid=(b1+e)/2;
ll left=sum1(2*node,b1,mid,L,R);
ll right=sum1(2*node+1,mid+1,e,L,R);
if(left==-1)
{
return right;
}
else if(right==-1)
{
return left;
}
else
{
if(a[left]>a[right])
{
return right;
}
else
{
return left;
}
}
}
void update(ll node,ll b1,ll e,ll ind,ll value)
{
if(b1==e)
{
segtree[node]=ind;
a[ind]=value;
}
else
{
ll mid=(b1+e)/2;
if(ind<=mid)
{
update(2*node,b1,mid,ind,value);
}
else
{
update(2*node+1,mid+1,e,ind,value);
}
ll l=segtree[2*node];
ll r=segtree[2*node+1];
if(a[l]>a[r])
{
segtree[node]=r;
}
else
{
segtree[node]=l;
}
}
}
int main()
{
ll n;
cin>>n;
ll i=1;
while(i<=n)
{
cin>>a[i];
b[i]=i;
i++;
}
build(1,1,n);
cout<<sum1(1,1,n,3,5);
cout<<"\n";
update( 1,1,n,3,100 );
cout<<sum1(1,1,n,3,5);
cout<<"\n";
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdHlwZWRlZiBsb25nIGxvbmcgaW50IGxsOwpsbCBsLHI7CmxsIHNlZ3RyZWVbNDAwMDAxXTsKbGwgYVsxMDAwMDFdOwpsbCBiWzEwMDAwMV07CnZvaWQgYnVpbGQobGwgbm9kZSxsbCBiMSxsbCBlKQogCntpZihiMT09ZSkKewogICAgc2VndHJlZVtub2RlXT1iW2IxXTsKY291dDw8YltiMV08PCJcbiI7Cn0KZWxzZQp7CiAgICBsbCBtaWQ9KGIxK2UpLzI7CiAKICBidWlsZCgyKm5vZGUsYjEsbWlkKTsKICBidWlsZCgyKm5vZGUrMSxtaWQrMSxlKTsKIAogCiAgbD1zZWd0cmVlWzIqbm9kZV07CiAgcj1zZWd0cmVlWzIqbm9kZSsxXTsKIAogIGlmKGFbbF08YVtyXSkKICB7CiAgICAgIHNlZ3RyZWVbbm9kZV09bDsKIAogIH0KICBlbHNlIGlmKGFbbF0+YVtyXSkKICB7CiAKICAgICAgc2VndHJlZVtub2RlXT1yOwogCiAgfQogIGVsc2UgaWYoYVtsXT09YVtyXSkKICB7CiAKICAgICAgc2VndHJlZVtub2RlXT1sOwogIH0KICBlbHNlCiAgewogCiAgfQogCn0KIAogCiAKfQpsbCBzdW0xKGxsIG5vZGUsbGwgYjEsbGwgZSxsbCBMLGxsIFIpCnsKIAogIGlmKGIxPlIgfHwgZTxMKQogIHsKICAgICAgICAgICAgcmV0dXJuIC0xOwogIH0KIAogIGlmIChiMT49TCAmJiBlPD1SKQogIHsKICAgICAgICAgICAgcmV0dXJuIHNlZ3RyZWVbbm9kZV07ICAKIAogIH0KIAogCmxsIG1pZD0oYjErZSkvMjsKIApsbCBsZWZ0PXN1bTEoMipub2RlLGIxLG1pZCxMLFIpOwpsbCByaWdodD1zdW0xKDIqbm9kZSsxLG1pZCsxLGUsTCxSKTsKaWYobGVmdD09LTEpCnsKICAgIHJldHVybiByaWdodDsKfQplbHNlIGlmKHJpZ2h0PT0tMSkKewogICAgcmV0dXJuIGxlZnQ7Cn0KZWxzZQp7CiAKICAgIGlmKGFbbGVmdF0+YVtyaWdodF0pCiAgICB7CiAgICAgICAgICAgIHJldHVybiByaWdodDsKICAgIH0KICAgIGVsc2UKICAgIHsKICAgICAgICByZXR1cm4gbGVmdDsKICAgIH0KIAogCn0KIAogCiAKIAogCiAKIAogCn0KCnZvaWQgdXBkYXRlKGxsIG5vZGUsbGwgYjEsbGwgZSxsbCBpbmQsbGwgdmFsdWUpCnsKCgoKaWYoYjE9PWUpCnsKICAgIAogICAgc2VndHJlZVtub2RlXT1pbmQ7CiAgICBhW2luZF09dmFsdWU7CiAgICAKICAgIAogICAgCiAgICAKfQplbHNlCnsKICAgIGxsIG1pZD0oYjErZSkvMjsKICAgIAogICAgaWYoaW5kPD1taWQpCiAgICB7CiAgICAgICAgdXBkYXRlKDIqbm9kZSxiMSxtaWQsaW5kLHZhbHVlKTsKICAgIH0KICAgIGVsc2UKICAgIHsKICAgICAgICAKICAgICAgICAKICAgICAgICB1cGRhdGUoMipub2RlKzEsbWlkKzEsZSxpbmQsdmFsdWUpOwogICAgICAgIAogICAgICAgIAogICAgICAgIAogICAgfQogICAgCiAgICAKICAgIGxsIGw9c2VndHJlZVsyKm5vZGVdOwogICAgbGwgcj1zZWd0cmVlWzIqbm9kZSsxXTsKICAgIAogICAgCiAgICBpZihhW2xdPmFbcl0pCiAgICB7CiAgICAgICAgCiAgICAgICAgc2VndHJlZVtub2RlXT1yOwogICAgICAgIAogICAgfQogICAgZWxzZQogICAgewogICAgICAgIAogICAgICAgIAogICAgICAgIHNlZ3RyZWVbbm9kZV09bDsKICAgICAgICAKICAgICAgICAKICAgIH0KICAgIAogICAgCiAgICAKICAgIAogICAgCiAgICAKICAgIAogICAgCiAgICAKICAgIAogICAgCn0KCgoKCgoKCgoKCgogICAgCiAgICAKCgoKICAgIAp9CgoKCgppbnQgbWFpbigpCnsKICAgIGxsIG47CiAgICBjaW4+Pm47CiAgICBsbCBpPTE7CiAgICB3aGlsZShpPD1uKQogICAgewogICAgICAgIGNpbj4+YVtpXTsKICAgICAgICBiW2ldPWk7CiAgICAgICAgaSsrOwogICAgfQogCiAgICBidWlsZCgxLDEsbik7CiAKIAogCiAgICBjb3V0PDxzdW0xKDEsMSxuLDMsNSk7CiBjb3V0PDwiXG4iOwogCiAgICB1cGRhdGUoIDEsMSxuLDMsMTAwICAgICAgICAgICAgKTsKICAgIAogICAgICBjb3V0PDxzdW0xKDEsMSxuLDMsNSk7CiAgICAgIGNvdXQ8PCJcbiI7CiAKIAogCiAKICAgIHJldHVybiAwOwp9CiA=