#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fast_IO ios::sync_with_stdio(false);
#define DEBUG fprintf(stderr,"Running on Line %d in Function %s\n",__LINE__,__FUNCTION__)
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define fir first
#define sec second
#define mod 998244353
#define int long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
inline int read()
{
char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
if(nega==-1) return -ans;
return ans;
}
typedef pair<int,int> pii;
void print(vector<int> x){for(int i=0;i<(int)x.size();i++) printf("%lld%c",x[i]," \n"[i==(int)x.size()-1]);}
#define N 100005
int a[N],n,Q;
struct Node
{
int pos,pre,cnt;
Node(int a=0,int b=0,int c=0) {pos=a,pre=b,cnt=c;}
};
struct SMT
{
#define ls (u<<1)
#define rs (u<<1|1)
#define mid ((l+r)/2)
vector<Node> vl[N*4],vr[N*4];
pair<vector<Node>,vector<Node>> merge(int l1,int r1,int l2,int r2,vector<Node> lpre,vector<Node> lsuf,vector<Node> rpre,vector<Node> rsuf)
{
vector<Node> pre,suf;
pre=lpre,suf=rsuf;
pre[(int)pre.size()-1].cnt=0;
suf[(int)suf.size()-1].cnt=0;
int lsum=pre.back().pre,rsum=suf.back().pre;
if(lsum>=a[l2]) pre.pop_back();
if(rsum>=a[r1]) suf.pop_back();
for(auto [pos,_pre,cnt]:rpre)
{
if(pos==r2||(lsum+_pre<a[pos+1])) pre.eb(pos,_pre+lsum,0);
}
for(auto [pos,_pre,cnt]:lsuf)
{
if(pos==l1||(rsum+_pre<a[pos-1])) suf.eb(pos,_pre+rsum,0);
}
{ // get lsuf jumps
vector<int> jmpr(lsuf.size()); int curpos=0;
for(int i=0;i<(int)lsuf.size();i++)
{
auto [pos,pre,cnt]=lsuf[i];
if(pre<a[r1+1]) {jmpr[i]=-1; continue;}
while(curpos+1<(int)rpre.size())
{
if(pre+rpre[curpos].pre>=a[rpre[curpos].pos+1]) curpos++;
else break;
}
jmpr[i]=curpos;
}
vector<int> tor(lsuf.size()),jmpl(lsuf.size());
for(int i=(int)lsuf.size()-1;i>=0;i--)
{
auto [pos,pre,cnt]=lsuf[i];
if(i==(int)lsuf.size()-1) tor[i]=jmpr[i],jmpl[i]=i;
else
{
int v=pre;
if(jmpr[i]!=-1) v+=rpre[jmpr[i]].pre;
if(v>=a[pos-1]) tor[i]=tor[i+1],jmpl[i]=jmpl[i+1];
else tor[i]=jmpr[i],jmpl[i]=i;
}
}
curpos=(int)pre.size()-1;
for(int i=(int)lsuf.size()-1;i>=0;i--)
{
if(jmpl[i]==(int)lsuf.size()-1)
{
int nedpos;
if(tor[i]==-1) nedpos=r1;
else nedpos=rpre[tor[i]].pos;
while(pre[curpos].pos!=nedpos) curpos--;
pre[curpos].cnt+=lsuf[i].cnt;
}
}
curpos=(int)suf.size()-1;
for(int i=(int)lsuf.size()-1;i>=0;i--)
{
if(tor[i]==(int)rpre.size()-1)
{
int nedpos=lsuf[jmpl[i]].pos;
while(suf[curpos].pos!=nedpos) curpos--;
suf[curpos].cnt+=lsuf[i].cnt;
}
}
// if(l1==1&&r2==5)
// {
// printf("***\n");
// print(tor),print(jmpl),print(jmpr);
// for(auto [x,y,z]:suf) printf("%d %d %d\n",x,y,z);
// }
}
{ // get rpre jumps
vector<int> jmpl(rpre.size()); int curpos=0;
for(int i=0;i<(int)rpre.size();i++)
{
auto [pos,pre,cnt]=rpre[i];
if(pre<a[r1]) {jmpl[i]=-1; continue;}
while(curpos+1<(int)lsuf.size())
{
if(pre+lsuf[curpos].pre>=a[lsuf[curpos].pos-1]) curpos++;
else break;
}
jmpl[i]=curpos;
}
vector<int> tol(rpre.size()),jmpr(rpre.size());
for(int i=(int)rpre.size()-1;i>=0;i--)
{
auto [pos,pre,cnt]=rpre[i];
if(i==(int)rpre.size()-1) tol[i]=jmpl[i],jmpr[i]=i;
else
{
int v=pre;
if(jmpl[i]!=-1) v+=lsuf[jmpl[i]].pre;
if(v>=a[pos+1]) tol[i]=tol[i+1],jmpr[i]=jmpr[i+1];
else tol[i]=jmpl[i],jmpr[i]=i;
}
}
curpos=(int)suf.size()-1;
for(int i=(int)rpre.size()-1;i>=0;i--)
{
if(jmpr[i]==(int)rpre.size()-1)
{
int nedpos;
if(tol[i]==-1) nedpos=l2;
else nedpos=lsuf[tol[i]].pos;
while(suf[curpos].pos!=nedpos) curpos--;
suf[curpos].cnt+=rpre[i].cnt;
}
}
curpos=(int)pre.size()-1;
for(int i=(int)rpre.size()-1;i>=0;i--)
{
if(tol[i]==(int)lsuf.size()-1)
{
int nedpos=rpre[jmpr[i]].pos;
while(pre[curpos].pos!=nedpos) curpos--;
pre[curpos].cnt+=rpre[i].cnt;
}
}
}
return {pre,suf};
}
pair<vector<Node>,vector<Node>> getone(int pos)
{
vector<Node> v;
v.eb(pos,a[pos],1);
return {v,v};
}
void build(int u,int l,int r)
{
if(l==r)
{
tie(vl[u],vr[u])=getone(l);
return ;
}
build(ls,l,mid),build(rs,mid+1,r);
tie(vl[u],vr[u])=merge(l,mid,mid+1,r,vl[ls],vr[ls],vl[rs],vr[rs]);
// printf("^ %d %d %d :\n",u,l,r);
// for(auto [x,y,z]:vl[u]) printf("%d %d %d\n",x,y,z);
// cout<<"\n";
// for(auto [x,y,z]:vr[u]) printf("%d %d %d\n",x,y,z);
// cout<<"\n";
}
void update(int u,int l,int r,int pos)
{
if(l==r)
{
tie(vl[u],vr[u])=getone(l);
return ;
}
if(pos<=mid) update(ls,l,mid,pos);
else update(rs,mid+1,r,pos);
tie(vl[u],vr[u])=merge(l,mid,mid+1,r,vl[ls],vr[ls],vl[rs],vr[rs]);
}
pair<vector<Node>,vector<Node>> query(int u,int l,int r,int L,int R)
{
if(L==l&&r==R) return {vl[u],vr[u]};
if(mid>=L&&mid<R)
{
auto [lpre,lsuf]=query(ls,l,mid,max(l,L),min(mid,R));
auto [rpre,rsuf]=query(rs,mid+1,r,max(mid+1,L),min(r,R));
return merge(L,mid,mid+1,R,lpre,lsuf,rpre,rsuf);
}
else if(mid>=L) return query(ls,l,mid,max(l,L),min(mid,R));
else if(mid<R) return query(rs,mid+1,r,max(mid+1,L),min(r,R));
else assert(0);
}
}smt;
signed main()
{
cin>>n;
for(int i=1;i<=n;i++) a[i]=read();
smt.build(1,1,n);
cin>>Q;
while(Q--)
{
int op=read(),l=read(),r=read();
if(op==1) a[l]=r,smt.update(1,1,n,l);
else
{
auto [pre,suf]=smt.query(1,1,n,l,r);
printf("%d\n",suf.back().cnt);
}
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBlYiBlbXBsYWNlX2JhY2sKI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSBGYXN0X0lPIGlvczo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKI2RlZmluZSBERUJVRyBmcHJpbnRmKHN0ZGVyciwiUnVubmluZyBvbiBMaW5lICVkIGluIEZ1bmN0aW9uICVzXG4iLF9fTElORV9fLF9fRlVOQ1RJT05fXykKLy9tdDE5OTM3IHJuZChjaHJvbm86OnN0ZWFkeV9jbG9jazo6bm93KCkudGltZV9zaW5jZV9lcG9jaCgpLmNvdW50KCkpOwojZGVmaW5lIGZpciBmaXJzdAojZGVmaW5lIHNlYyBzZWNvbmQKI2RlZmluZSBtb2QgOTk4MjQ0MzUzCiNkZWZpbmUgaW50IGxvbmcgbG9uZwojZGVmaW5lIGluZiAweDNmM2YzZjNmCiNkZWZpbmUgSU5GIDB4M2YzZjNmM2YzZjNmM2YzZgppbmxpbmUgaW50IHJlYWQoKQp7CgljaGFyIGNoPWdldGNoYXIoKTsgaW50IG5lZ2E9MTsgd2hpbGUoIWlzZGlnaXQoY2gpKSB7aWYoY2g9PSctJykgbmVnYT0tMTsgY2g9Z2V0Y2hhcigpO30KCWludCBhbnM9MDsgd2hpbGUoaXNkaWdpdChjaCkpIHthbnM9YW5zKjEwK2NoLTQ4O2NoPWdldGNoYXIoKTt9CglpZihuZWdhPT0tMSkgcmV0dXJuIC1hbnM7CglyZXR1cm4gYW5zOwp9CnR5cGVkZWYgcGFpcjxpbnQsaW50PiBwaWk7CnZvaWQgcHJpbnQodmVjdG9yPGludD4geCl7Zm9yKGludCBpPTA7aTwoaW50KXguc2l6ZSgpO2krKykgcHJpbnRmKCIlbGxkJWMiLHhbaV0sIiBcbiJbaT09KGludCl4LnNpemUoKS0xXSk7fQojZGVmaW5lIE4gMTAwMDA1CmludCBhW05dLG4sUTsKc3RydWN0IE5vZGUKewoJaW50IHBvcyxwcmUsY250OwoJTm9kZShpbnQgYT0wLGludCBiPTAsaW50IGM9MCkge3Bvcz1hLHByZT1iLGNudD1jO30KfTsKc3RydWN0IFNNVAp7CgkjZGVmaW5lIGxzICh1PDwxKQoJI2RlZmluZSBycyAodTw8MXwxKQoJI2RlZmluZSBtaWQgKChsK3IpLzIpCgl2ZWN0b3I8Tm9kZT4gdmxbTio0XSx2cltOKjRdOwoJcGFpcjx2ZWN0b3I8Tm9kZT4sdmVjdG9yPE5vZGU+PiBtZXJnZShpbnQgbDEsaW50IHIxLGludCBsMixpbnQgcjIsdmVjdG9yPE5vZGU+IGxwcmUsdmVjdG9yPE5vZGU+IGxzdWYsdmVjdG9yPE5vZGU+IHJwcmUsdmVjdG9yPE5vZGU+IHJzdWYpCgl7CgkJdmVjdG9yPE5vZGU+IHByZSxzdWY7CgkJcHJlPWxwcmUsc3VmPXJzdWY7CgkJcHJlWyhpbnQpcHJlLnNpemUoKS0xXS5jbnQ9MDsKCQlzdWZbKGludClzdWYuc2l6ZSgpLTFdLmNudD0wOwoJCWludCBsc3VtPXByZS5iYWNrKCkucHJlLHJzdW09c3VmLmJhY2soKS5wcmU7CgkJaWYobHN1bT49YVtsMl0pIHByZS5wb3BfYmFjaygpOwoJCWlmKHJzdW0+PWFbcjFdKSBzdWYucG9wX2JhY2soKTsKCQlmb3IoYXV0byBbcG9zLF9wcmUsY250XTpycHJlKQoJCXsKCQkJaWYocG9zPT1yMnx8KGxzdW0rX3ByZTxhW3BvcysxXSkpIHByZS5lYihwb3MsX3ByZStsc3VtLDApOwoJCX0KCQlmb3IoYXV0byBbcG9zLF9wcmUsY250XTpsc3VmKQoJCXsKCQkJaWYocG9zPT1sMXx8KHJzdW0rX3ByZTxhW3Bvcy0xXSkpIHN1Zi5lYihwb3MsX3ByZStyc3VtLDApOwoJCX0KCQl7IC8vIGdldCBsc3VmIGp1bXBzCgkJCXZlY3RvcjxpbnQ+IGptcHIobHN1Zi5zaXplKCkpOyBpbnQgY3VycG9zPTA7CgkJCWZvcihpbnQgaT0wO2k8KGludClsc3VmLnNpemUoKTtpKyspCgkJCXsKCQkJCWF1dG8gW3BvcyxwcmUsY250XT1sc3VmW2ldOwoJCQkJaWYocHJlPGFbcjErMV0pIHtqbXByW2ldPS0xOyBjb250aW51ZTt9CgkJCQl3aGlsZShjdXJwb3MrMTwoaW50KXJwcmUuc2l6ZSgpKQoJCQkJewoJCQkJCWlmKHByZStycHJlW2N1cnBvc10ucHJlPj1hW3JwcmVbY3VycG9zXS5wb3MrMV0pIGN1cnBvcysrOwoJCQkJCWVsc2UgYnJlYWs7CgkJCQl9CgkJCQlqbXByW2ldPWN1cnBvczsKCQkJfQoJCQl2ZWN0b3I8aW50PiB0b3IobHN1Zi5zaXplKCkpLGptcGwobHN1Zi5zaXplKCkpOwoJCQlmb3IoaW50IGk9KGludClsc3VmLnNpemUoKS0xO2k+PTA7aS0tKQoJCQl7CgkJCQlhdXRvIFtwb3MscHJlLGNudF09bHN1ZltpXTsKCQkJCWlmKGk9PShpbnQpbHN1Zi5zaXplKCktMSkgdG9yW2ldPWptcHJbaV0sam1wbFtpXT1pOwoJCQkJZWxzZQoJCQkJewoJCQkJCWludCB2PXByZTsKCQkJCQlpZihqbXByW2ldIT0tMSkgdis9cnByZVtqbXByW2ldXS5wcmU7CgkJCQkJaWYodj49YVtwb3MtMV0pIHRvcltpXT10b3JbaSsxXSxqbXBsW2ldPWptcGxbaSsxXTsKCQkJCQllbHNlIHRvcltpXT1qbXByW2ldLGptcGxbaV09aTsKCQkJCX0KCQkJfQoJCQljdXJwb3M9KGludClwcmUuc2l6ZSgpLTE7CgkJCWZvcihpbnQgaT0oaW50KWxzdWYuc2l6ZSgpLTE7aT49MDtpLS0pCgkJCXsKCQkJCWlmKGptcGxbaV09PShpbnQpbHN1Zi5zaXplKCktMSkKCQkJCXsKCQkJCQlpbnQgbmVkcG9zOwoJCQkJCWlmKHRvcltpXT09LTEpIG5lZHBvcz1yMTsKCQkJCQllbHNlIG5lZHBvcz1ycHJlW3RvcltpXV0ucG9zOwoJCQkJCXdoaWxlKHByZVtjdXJwb3NdLnBvcyE9bmVkcG9zKSBjdXJwb3MtLTsKCQkJCQlwcmVbY3VycG9zXS5jbnQrPWxzdWZbaV0uY250OwoJCQkJfQoJCQl9CgkJCWN1cnBvcz0oaW50KXN1Zi5zaXplKCktMTsKCQkJZm9yKGludCBpPShpbnQpbHN1Zi5zaXplKCktMTtpPj0wO2ktLSkKCQkJewoJCQkJaWYodG9yW2ldPT0oaW50KXJwcmUuc2l6ZSgpLTEpCgkJCQl7CgkJCQkJaW50IG5lZHBvcz1sc3VmW2ptcGxbaV1dLnBvczsKCQkJCQl3aGlsZShzdWZbY3VycG9zXS5wb3MhPW5lZHBvcykgY3VycG9zLS07CgkJCQkJc3VmW2N1cnBvc10uY250Kz1sc3VmW2ldLmNudDsKCQkJCX0KCQkJfQoJCQkvLyBpZihsMT09MSYmcjI9PTUpCgkJCS8vIHsKCQkJCS8vIHByaW50ZigiKioqXG4iKTsKCQkJCS8vIHByaW50KHRvcikscHJpbnQoam1wbCkscHJpbnQoam1wcik7CgkJCQkvLyBmb3IoYXV0byBbeCx5LHpdOnN1ZikgcHJpbnRmKCIlZCAlZCAlZFxuIix4LHkseik7CgkJCS8vIH0KCQl9CgkJeyAvLyBnZXQgcnByZSBqdW1wcwoJCQl2ZWN0b3I8aW50PiBqbXBsKHJwcmUuc2l6ZSgpKTsgaW50IGN1cnBvcz0wOwoJCQlmb3IoaW50IGk9MDtpPChpbnQpcnByZS5zaXplKCk7aSsrKQoJCQl7CgkJCQlhdXRvIFtwb3MscHJlLGNudF09cnByZVtpXTsKCQkJCWlmKHByZTxhW3IxXSkge2ptcGxbaV09LTE7IGNvbnRpbnVlO30KCQkJCXdoaWxlKGN1cnBvcysxPChpbnQpbHN1Zi5zaXplKCkpCgkJCQl7CgkJCQkJaWYocHJlK2xzdWZbY3VycG9zXS5wcmU+PWFbbHN1ZltjdXJwb3NdLnBvcy0xXSkgY3VycG9zKys7CgkJCQkJZWxzZSBicmVhazsKCQkJCX0KCQkJCWptcGxbaV09Y3VycG9zOwoJCQl9CgkJCXZlY3RvcjxpbnQ+IHRvbChycHJlLnNpemUoKSksam1wcihycHJlLnNpemUoKSk7CgkJCWZvcihpbnQgaT0oaW50KXJwcmUuc2l6ZSgpLTE7aT49MDtpLS0pCgkJCXsKCQkJCWF1dG8gW3BvcyxwcmUsY250XT1ycHJlW2ldOwoJCQkJaWYoaT09KGludClycHJlLnNpemUoKS0xKSB0b2xbaV09am1wbFtpXSxqbXByW2ldPWk7CgkJCQllbHNlCgkJCQl7CgkJCQkJaW50IHY9cHJlOwoJCQkJCWlmKGptcGxbaV0hPS0xKSB2Kz1sc3VmW2ptcGxbaV1dLnByZTsKCQkJCQlpZih2Pj1hW3BvcysxXSkgdG9sW2ldPXRvbFtpKzFdLGptcHJbaV09am1wcltpKzFdOwoJCQkJCWVsc2UgdG9sW2ldPWptcGxbaV0sam1wcltpXT1pOwoJCQkJfQoJCQl9CgkJCWN1cnBvcz0oaW50KXN1Zi5zaXplKCktMTsKCQkJZm9yKGludCBpPShpbnQpcnByZS5zaXplKCktMTtpPj0wO2ktLSkKCQkJewoJCQkJaWYoam1wcltpXT09KGludClycHJlLnNpemUoKS0xKQoJCQkJewoJCQkJCWludCBuZWRwb3M7CgkJCQkJaWYodG9sW2ldPT0tMSkgbmVkcG9zPWwyOwoJCQkJCWVsc2UgbmVkcG9zPWxzdWZbdG9sW2ldXS5wb3M7CgkJCQkJd2hpbGUoc3VmW2N1cnBvc10ucG9zIT1uZWRwb3MpIGN1cnBvcy0tOwoJCQkJCXN1ZltjdXJwb3NdLmNudCs9cnByZVtpXS5jbnQ7CgkJCQl9CgkJCX0KCQkJY3VycG9zPShpbnQpcHJlLnNpemUoKS0xOwoJCQlmb3IoaW50IGk9KGludClycHJlLnNpemUoKS0xO2k+PTA7aS0tKQoJCQl7CgkJCQlpZih0b2xbaV09PShpbnQpbHN1Zi5zaXplKCktMSkKCQkJCXsKCQkJCQlpbnQgbmVkcG9zPXJwcmVbam1wcltpXV0ucG9zOwoJCQkJCXdoaWxlKHByZVtjdXJwb3NdLnBvcyE9bmVkcG9zKSBjdXJwb3MtLTsKCQkJCQlwcmVbY3VycG9zXS5jbnQrPXJwcmVbaV0uY250OwoJCQkJfQoJCQl9CgkJfQoJCXJldHVybiB7cHJlLHN1Zn07Cgl9CglwYWlyPHZlY3RvcjxOb2RlPix2ZWN0b3I8Tm9kZT4+IGdldG9uZShpbnQgcG9zKQoJewoJCXZlY3RvcjxOb2RlPiB2OwoJCXYuZWIocG9zLGFbcG9zXSwxKTsKCQlyZXR1cm4ge3Ysdn07Cgl9Cgl2b2lkIGJ1aWxkKGludCB1LGludCBsLGludCByKQoJewoJCWlmKGw9PXIpCgkJewoJCQl0aWUodmxbdV0sdnJbdV0pPWdldG9uZShsKTsKCQkJcmV0dXJuIDsKCQl9CgkJYnVpbGQobHMsbCxtaWQpLGJ1aWxkKHJzLG1pZCsxLHIpOwoJCXRpZSh2bFt1XSx2clt1XSk9bWVyZ2UobCxtaWQsbWlkKzEscix2bFtsc10sdnJbbHNdLHZsW3JzXSx2cltyc10pOwoJCS8vIHByaW50ZigiXiAlZCAlZCAlZCA6XG4iLHUsbCxyKTsKCQkvLyBmb3IoYXV0byBbeCx5LHpdOnZsW3VdKSBwcmludGYoIiVkICVkICVkXG4iLHgseSx6KTsKCQkvLyBjb3V0PDwiXG4iOwoJCS8vIGZvcihhdXRvIFt4LHksel06dnJbdV0pIHByaW50ZigiJWQgJWQgJWRcbiIseCx5LHopOwoJCS8vIGNvdXQ8PCJcbiI7Cgl9Cgl2b2lkIHVwZGF0ZShpbnQgdSxpbnQgbCxpbnQgcixpbnQgcG9zKQoJewoJCWlmKGw9PXIpCgkJewoJCQl0aWUodmxbdV0sdnJbdV0pPWdldG9uZShsKTsKCQkJcmV0dXJuIDsKCQl9CgkJaWYocG9zPD1taWQpIHVwZGF0ZShscyxsLG1pZCxwb3MpOwoJCWVsc2UgdXBkYXRlKHJzLG1pZCsxLHIscG9zKTsKCQl0aWUodmxbdV0sdnJbdV0pPW1lcmdlKGwsbWlkLG1pZCsxLHIsdmxbbHNdLHZyW2xzXSx2bFtyc10sdnJbcnNdKTsKCX0KCXBhaXI8dmVjdG9yPE5vZGU+LHZlY3RvcjxOb2RlPj4gcXVlcnkoaW50IHUsaW50IGwsaW50IHIsaW50IEwsaW50IFIpCgl7CgkJaWYoTD09bCYmcj09UikgcmV0dXJuIHt2bFt1XSx2clt1XX07CgkJaWYobWlkPj1MJiZtaWQ8UikKCQl7CgkJCWF1dG8gW2xwcmUsbHN1Zl09cXVlcnkobHMsbCxtaWQsbWF4KGwsTCksbWluKG1pZCxSKSk7CgkJCWF1dG8gW3JwcmUscnN1Zl09cXVlcnkocnMsbWlkKzEscixtYXgobWlkKzEsTCksbWluKHIsUikpOwoJCQlyZXR1cm4gbWVyZ2UoTCxtaWQsbWlkKzEsUixscHJlLGxzdWYscnByZSxyc3VmKTsKCQl9CgkJZWxzZSBpZihtaWQ+PUwpIHJldHVybiBxdWVyeShscyxsLG1pZCxtYXgobCxMKSxtaW4obWlkLFIpKTsKCQllbHNlIGlmKG1pZDxSKSByZXR1cm4gcXVlcnkocnMsbWlkKzEscixtYXgobWlkKzEsTCksbWluKHIsUikpOwoJCWVsc2UgYXNzZXJ0KDApOwoJfQp9c210OwpzaWduZWQgbWFpbigpCnsKCWNpbj4+bjsKCWZvcihpbnQgaT0xO2k8PW47aSsrKSBhW2ldPXJlYWQoKTsKCXNtdC5idWlsZCgxLDEsbik7CgljaW4+PlE7Cgl3aGlsZShRLS0pCgl7CgkJaW50IG9wPXJlYWQoKSxsPXJlYWQoKSxyPXJlYWQoKTsKCQlpZihvcD09MSkgYVtsXT1yLHNtdC51cGRhdGUoMSwxLG4sbCk7CgkJZWxzZQoJCXsKCQkJYXV0byBbcHJlLHN1Zl09c210LnF1ZXJ5KDEsMSxuLGwscik7CgkJCXByaW50ZigiJWRcbiIsc3VmLmJhY2soKS5jbnQpOwoJCX0KCX0KCXJldHVybiAwOwp9Cgo=