#include<bits/stdc++.h>
using namespace std;
typedef int ll;
template <typename T>
inline void in(T &a) {
register T c;
a = 0;
do c = getchar_unlocked(); while(c < '0');
do {
a = (a << 1) + (a << 3) + c - '0';
c = getchar_unlocked();
} while (c >= '0');
}
template <typename T>
inline void pr(T a) {
char s[11];
T t = -1;
do {
s[++t] = a % 10 + '0';
a /= 10;
} while (a > 0);
while (t >= 0) putchar_unlocked(s[t--]);
putchar_unlocked('\n');
}
struct node
{
ll key,prio,size;
node* left,*right;
};
struct alone
{
node* root=NULL;
node* create(ll x)
{
node* p=new node;
p->key=x;
p->prio=rand();
p->size=1;
p->left=NULL;
p->right=NULL;
return p;
}
ll usize(node* p)
{
if(p)
return p->size;
return 0;
}
void nsize(node* p)
{
p->size=1+usize(p->left)+usize(p->right);
}
pair<node*,node*>split(node* root,ll x)
{
if(root==NULL)
return make_pair(root,root);
if(root->key<=x)
{
pair<node*,node*>p=split(root->right,x);
root->right=p.first;
if(root)
nsize(root);
if(p.second)
nsize(p.second);
return make_pair(root,p.second);
}
pair<node*,node*>p=split(root->left,x);
root->left=p.second;
if(root)
nsize(root);
if(p.first)
nsize(p.first);
return make_pair(p.first,root);
}
node* merge(node* root1,node* root2)
{
if(root1==NULL||root2==NULL)
return (root1==NULL)?root2:root1;
if(root1->prio>root2->prio)
{
node* p=merge(root1->right,root2);
root1->right=p;
if(root1)
nsize(root1);
return root1;
}
node* p=merge(root1,root2->left);
root2->left=p;
if(root2)
nsize(root2);
return root2;
}
node* insert(node* root,ll x)
{
node* tmp=create(x);
pair<node*,node*>p=split(root,x);
node* p1=merge(p.first,tmp);
if(p1)
nsize(p1);
node* p2=merge(p1,p.second);
if(p2)
nsize(p2);
return p2;
}
node* del(node* root,ll x)
{
if(root==NULL)
return root;
if(root->key==x)
{
node* p=merge(root->left,root->right);
delete root;
if(p)
nsize(p);
return p;
}
if(root->key<x)
root->right=del(root->right,x);
else
root->left=del(root->left,x);
if(root)
nsize(root);
return root;
}
ll count(node* root,ll k,ll val)
{
if(root==NULL)
return val;
if(root->key==k)
return val+usize(root->left);
if(root->key<k)
return count(root->right,k,val+usize(root->left)+1);
return count(root->left,k,val);
}
}seg[4000005];
void build(ll s,ll e,ll p,ll indx,ll val)
{
if(s==e)
{
seg[p].root=seg[p].insert(seg[p].root,val);
return;
}
ll mid=(s+e)/2;
if(indx<=mid)
{
build(s,mid,2*p+1,indx,val);
seg[p].root=seg[p].insert(seg[p].root,val);
}
else
{
build(mid+1,e,2*p+2,indx,val);
seg[p].root=seg[p].insert(seg[p].root,val);
}
}
void update(ll s,ll e,ll p,ll indx,ll val)
{
if(s==e)
{
seg[p].root=seg[p].del(seg[p].root,val);
return;
}
ll mid=(s+e)/2;
if(indx<=mid)
{
update(s,mid,2*p+1,indx,val);
seg[p].root=seg[p].del(seg[p].root,val);
}
else
{
update(mid+1,e,2*p+2,indx,val);
seg[p].root=seg[p].del(seg[p].root,val);
}
}
ll querry(ll s,ll e,ll p,ll ql,ll qh,ll x)
{
if(s>qh||e<ql)
return 0;
if(s>=ql&&e<=qh)
{
ll u=seg[p].count(seg[p].root,x,0);
ll z=seg[p].usize(seg[p].root);
return z-u;
}
ll mid=(s+e)/2;
ll k1=querry(s,mid,2*p+1,ql,qh,x);
ll k2=querry(mid+1,e,2*p+2,ql,qh,x);
return k1+k2;
}
int main()
{
ll n,i,q,qt,l,r,x;
in(n);
ll a[n];
for(i=0;i<n;i++)
{
in(a[i]);
build(0,n-1,0,i,a[i]);
}
in(q);
while(q--)
{
in(qt);
if(qt==0)
{
in(l);
in(r);
in(x);
l--;
r--;
ll ans=querry(0,n-1,0,l,r,x);
pr(ans);
}
else
{
in(l);
in(x);
l--;
update(0,n-1,0,l,a[l]);
a[l]=x;
build(0,n-1,0,l,a[l]);
}
}
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdHlwZWRlZiBpbnQgbGw7CnRlbXBsYXRlIDx0eXBlbmFtZSBUPgppbmxpbmUgdm9pZCBpbihUICZhKSB7CglyZWdpc3RlciBUIGM7CglhID0gMDsKCWRvIGMgPSBnZXRjaGFyX3VubG9ja2VkKCk7IHdoaWxlKGMgPCAnMCcpOwoJZG8gewoJCWEgPSAoYSA8PCAxKSArIChhIDw8IDMpICsgYyAtICcwJzsKCQljID0gZ2V0Y2hhcl91bmxvY2tlZCgpOwoJfSB3aGlsZSAoYyA+PSAnMCcpOwp9CnRlbXBsYXRlIDx0eXBlbmFtZSBUPgppbmxpbmUgdm9pZCBwcihUIGEpIHsKCWNoYXIgc1sxMV07CglUIHQgPSAtMTsKCWRvIHsKCQlzWysrdF0gPSBhICUgMTAgKyAnMCc7CgkJYSAvPSAxMDsKCX0gd2hpbGUgKGEgPiAwKTsKCXdoaWxlICh0ID49IDApIHB1dGNoYXJfdW5sb2NrZWQoc1t0LS1dKTsKCXB1dGNoYXJfdW5sb2NrZWQoJ1xuJyk7Cn0Kc3RydWN0IG5vZGUKewogICAgbGwga2V5LHByaW8sc2l6ZTsKICAgIG5vZGUqIGxlZnQsKnJpZ2h0Owp9OwpzdHJ1Y3QgYWxvbmUKewogICAgbm9kZSogcm9vdD1OVUxMOwogICAgbm9kZSogY3JlYXRlKGxsIHgpCiAgICB7CiAgICAgICAgbm9kZSogcD1uZXcgbm9kZTsKICAgICAgICBwLT5rZXk9eDsKICAgICAgICBwLT5wcmlvPXJhbmQoKTsKICAgICAgICBwLT5zaXplPTE7CiAgICAgICAgcC0+bGVmdD1OVUxMOwogICAgICAgIHAtPnJpZ2h0PU5VTEw7CiAgICAgICAgcmV0dXJuIHA7CiAgICB9CiAgICBsbCB1c2l6ZShub2RlKiBwKQogICAgewogICAgICAgIGlmKHApCiAgICAgICAgcmV0dXJuIHAtPnNpemU7CiAgICAgICAgcmV0dXJuIDA7CiAgICB9CiAgICB2b2lkIG5zaXplKG5vZGUqIHApCiAgICB7CiAgICAgICAgcC0+c2l6ZT0xK3VzaXplKHAtPmxlZnQpK3VzaXplKHAtPnJpZ2h0KTsKICAgIH0KICAgIHBhaXI8bm9kZSosbm9kZSo+c3BsaXQobm9kZSogcm9vdCxsbCB4KQogICAgewogICAgICAgIGlmKHJvb3Q9PU5VTEwpCiAgICAgICAgcmV0dXJuIG1ha2VfcGFpcihyb290LHJvb3QpOwogICAgICAgIGlmKHJvb3QtPmtleTw9eCkKICAgICAgICB7CiAgICAgICAgICAgIHBhaXI8bm9kZSosbm9kZSo+cD1zcGxpdChyb290LT5yaWdodCx4KTsKICAgICAgICAgICAgcm9vdC0+cmlnaHQ9cC5maXJzdDsKICAgICAgICAgICAgaWYocm9vdCkKICAgICAgICAgICAgbnNpemUocm9vdCk7CiAgICAgICAgICAgIGlmKHAuc2Vjb25kKQogICAgICAgICAgICBuc2l6ZShwLnNlY29uZCk7CiAgICAgICAgICAgIHJldHVybiBtYWtlX3BhaXIocm9vdCxwLnNlY29uZCk7CiAgICAgICAgfQogICAgICAgIHBhaXI8bm9kZSosbm9kZSo+cD1zcGxpdChyb290LT5sZWZ0LHgpOwogICAgICAgIHJvb3QtPmxlZnQ9cC5zZWNvbmQ7CiAgICAgICAgaWYocm9vdCkKICAgICAgICBuc2l6ZShyb290KTsKICAgICAgICBpZihwLmZpcnN0KQogICAgICAgIG5zaXplKHAuZmlyc3QpOwogICAgICAgIHJldHVybiBtYWtlX3BhaXIocC5maXJzdCxyb290KTsKICAgIH0KICAgIG5vZGUqIG1lcmdlKG5vZGUqIHJvb3QxLG5vZGUqIHJvb3QyKQogICAgewogICAgICAgIGlmKHJvb3QxPT1OVUxMfHxyb290Mj09TlVMTCkKICAgICAgICByZXR1cm4gKHJvb3QxPT1OVUxMKT9yb290Mjpyb290MTsKICAgICAgICBpZihyb290MS0+cHJpbz5yb290Mi0+cHJpbykKICAgICAgICB7CiAgICAgICAgICAgIG5vZGUqIHA9bWVyZ2Uocm9vdDEtPnJpZ2h0LHJvb3QyKTsKICAgICAgICAgICAgcm9vdDEtPnJpZ2h0PXA7CiAgICAgICAgICAgIGlmKHJvb3QxKQogICAgICAgICAgICBuc2l6ZShyb290MSk7CiAgICAgICAgICAgIHJldHVybiByb290MTsKICAgICAgICB9CiAgICAgICAgbm9kZSogcD1tZXJnZShyb290MSxyb290Mi0+bGVmdCk7CiAgICAgICAgcm9vdDItPmxlZnQ9cDsKICAgICAgICBpZihyb290MikKICAgICAgICBuc2l6ZShyb290Mik7CiAgICAgICAgcmV0dXJuIHJvb3QyOwogICAgfQogICAgbm9kZSogaW5zZXJ0KG5vZGUqIHJvb3QsbGwgeCkKICAgIHsKICAgICAgICBub2RlKiB0bXA9Y3JlYXRlKHgpOwogICAgICAgIHBhaXI8bm9kZSosbm9kZSo+cD1zcGxpdChyb290LHgpOwogICAgICAgIG5vZGUqIHAxPW1lcmdlKHAuZmlyc3QsdG1wKTsKICAgICAgICBpZihwMSkKICAgICAgICBuc2l6ZShwMSk7CiAgICAgICAgbm9kZSogcDI9bWVyZ2UocDEscC5zZWNvbmQpOwogICAgICAgIGlmKHAyKQogICAgICAgIG5zaXplKHAyKTsKICAgICAgICByZXR1cm4gcDI7CiAgICB9CiAgICBub2RlKiBkZWwobm9kZSogcm9vdCxsbCB4KQogICAgewogICAgICAgIGlmKHJvb3Q9PU5VTEwpCiAgICAgICAgcmV0dXJuIHJvb3Q7CiAgICAgICAgaWYocm9vdC0+a2V5PT14KQogICAgICAgIHsKICAgICAgICAgICAgbm9kZSogcD1tZXJnZShyb290LT5sZWZ0LHJvb3QtPnJpZ2h0KTsKICAgICAgICAgICAgZGVsZXRlIHJvb3Q7CiAgICAgICAgICAgIGlmKHApCiAgICAgICAgICAgIG5zaXplKHApOwogICAgICAgICAgICByZXR1cm4gcDsKICAgICAgICB9CiAgICAgICAgaWYocm9vdC0+a2V5PHgpCiAgICAgICAgcm9vdC0+cmlnaHQ9ZGVsKHJvb3QtPnJpZ2h0LHgpOwogICAgICAgIGVsc2UKICAgICAgICByb290LT5sZWZ0PWRlbChyb290LT5sZWZ0LHgpOwogICAgICAgIGlmKHJvb3QpCiAgICAgICAgbnNpemUocm9vdCk7CiAgICAgICAgcmV0dXJuIHJvb3Q7CiAgICB9CiAgICBsbCBjb3VudChub2RlKiByb290LGxsIGssbGwgdmFsKQogICAgewogICAgICAgIGlmKHJvb3Q9PU5VTEwpCiAgICAgICAgcmV0dXJuIHZhbDsKICAgICAgICBpZihyb290LT5rZXk9PWspCiAgICAgICAgcmV0dXJuIHZhbCt1c2l6ZShyb290LT5sZWZ0KTsKICAgICAgICBpZihyb290LT5rZXk8aykKICAgICAgICByZXR1cm4gY291bnQocm9vdC0+cmlnaHQsayx2YWwrdXNpemUocm9vdC0+bGVmdCkrMSk7CiAgICAgICAgcmV0dXJuIGNvdW50KHJvb3QtPmxlZnQsayx2YWwpOwogICAgfQp9c2VnWzQwMDAwMDVdOwp2b2lkIGJ1aWxkKGxsIHMsbGwgZSxsbCBwLGxsIGluZHgsbGwgdmFsKQp7CiAgICBpZihzPT1lKQogICAgewogICAgICAgIHNlZ1twXS5yb290PXNlZ1twXS5pbnNlcnQoc2VnW3BdLnJvb3QsdmFsKTsKICAgICAgICByZXR1cm47CiAgICB9CiAgICBsbCBtaWQ9KHMrZSkvMjsKICAgIGlmKGluZHg8PW1pZCkKICAgIHsKICAgICAgICBidWlsZChzLG1pZCwyKnArMSxpbmR4LHZhbCk7CiAgICAgICAgc2VnW3BdLnJvb3Q9c2VnW3BdLmluc2VydChzZWdbcF0ucm9vdCx2YWwpOwogICAgfQogICAgZWxzZQogICAgewogICAgICAgIGJ1aWxkKG1pZCsxLGUsMipwKzIsaW5keCx2YWwpOwogICAgICAgIHNlZ1twXS5yb290PXNlZ1twXS5pbnNlcnQoc2VnW3BdLnJvb3QsdmFsKTsKICAgIH0KfQp2b2lkIHVwZGF0ZShsbCBzLGxsIGUsbGwgcCxsbCBpbmR4LGxsIHZhbCkKewogICAgaWYocz09ZSkKICAgIHsKICAgICAgICBzZWdbcF0ucm9vdD1zZWdbcF0uZGVsKHNlZ1twXS5yb290LHZhbCk7CiAgICAgICAgcmV0dXJuOwogICAgfQogICAgbGwgbWlkPShzK2UpLzI7CiAgICBpZihpbmR4PD1taWQpCiAgICB7CiAgICAgICAgdXBkYXRlKHMsbWlkLDIqcCsxLGluZHgsdmFsKTsKICAgICAgICBzZWdbcF0ucm9vdD1zZWdbcF0uZGVsKHNlZ1twXS5yb290LHZhbCk7CiAgICB9CiAgICBlbHNlCiAgICB7CiAgICAgICAgdXBkYXRlKG1pZCsxLGUsMipwKzIsaW5keCx2YWwpOwogICAgICAgIHNlZ1twXS5yb290PXNlZ1twXS5kZWwoc2VnW3BdLnJvb3QsdmFsKTsKICAgIH0KfQpsbCBxdWVycnkobGwgcyxsbCBlLGxsIHAsbGwgcWwsbGwgcWgsbGwgeCkKewogICAgaWYocz5xaHx8ZTxxbCkKICAgIHJldHVybiAwOwogICAgaWYocz49cWwmJmU8PXFoKQogICAgewogICAgICAgIGxsIHU9c2VnW3BdLmNvdW50KHNlZ1twXS5yb290LHgsMCk7CiAgICAgICAgbGwgej1zZWdbcF0udXNpemUoc2VnW3BdLnJvb3QpOwogICAgICAgIHJldHVybiB6LXU7CiAgICB9CiAgICBsbCBtaWQ9KHMrZSkvMjsKICAgIGxsIGsxPXF1ZXJyeShzLG1pZCwyKnArMSxxbCxxaCx4KTsKICAgIGxsIGsyPXF1ZXJyeShtaWQrMSxlLDIqcCsyLHFsLHFoLHgpOwogICAgcmV0dXJuIGsxK2syOwp9CmludCBtYWluKCkKewogICAgbGwgbixpLHEscXQsbCxyLHg7CiAgICBpbihuKTsKICAgIGxsIGFbbl07CiAgICBmb3IoaT0wO2k8bjtpKyspCiAgICB7CiAgICAgICAgaW4oYVtpXSk7CiAgICAgICAgYnVpbGQoMCxuLTEsMCxpLGFbaV0pOwogICAgfQogICAgaW4ocSk7CiAgICB3aGlsZShxLS0pCiAgICB7CiAgICAgICAgaW4ocXQpOwogICAgICAgIGlmKHF0PT0wKQogICAgICAgIHsKICAgICAgICAgICAgaW4obCk7CiAgICAgICAgICAgIGluKHIpOwogICAgICAgICAgICBpbih4KTsKICAgICAgICAgICAgbC0tOwogICAgICAgICAgICByLS07CiAgICAgICAgICAgIGxsIGFucz1xdWVycnkoMCxuLTEsMCxsLHIseCk7CiAgICAgICAgICAgIHByKGFucyk7CiAgICAgICAgfQogICAgICAgIGVsc2UKICAgICAgICB7CiAgICAgICAgICAgIGluKGwpOwogICAgICAgICAgICBpbih4KTsKICAgICAgICAgICAgbC0tOwogICAgICAgICAgICB1cGRhdGUoMCxuLTEsMCxsLGFbbF0pOwogICAgICAgICAgICBhW2xdPXg7CiAgICAgICAgICAgIGJ1aWxkKDAsbi0xLDAsbCxhW2xdKTsKICAgICAgICB9CiAgICB9Cn0=