import java.util.*;
import java.io.*;
class KQUERY2{
static class Node{
int val;
Node left;
Node right;
int count;
int sum;
Node(int val){
this.val = val;
count = 1;
sum = 1;
left = null;
right = null;
}
}
static int n ;
static int []a;
static Node []st;
static int count;
InputReader in
= new InputReader
(System.
in); OutputWriter out
= new OutputWriter
(System.
out); n = in.readInt();
a = new int[n];
for(int i=0;i<n;i++){
a[i] = in.readInt();
}
st = new Node[4*n];
constructST(0,n-1,0);
int m = in.readInt();
while(m-- >0){
int flag = in.readInt();
if(flag == 0){
int ind = in.readInt()-1;
int val = in.readInt();
updateST(0,n-1,ind,val,0);
}else{
int l = in.readInt()-1;
int r = in.readInt()-1;
int k = in.readInt();
count = 0;
query(0,n-1,l,r,k,0);
}
}
}
static void inOrder(Node root){
if(root == null){
return ;
}
if(root.left != null){
inOrder(root.left);
}
System.
out.
print(root.
val+" "); if(root.right != null){
inOrder(root.right);
}
}
static void query(int s,int e,int l,int r,int k,int i){
if(l > e || r < s){
return ;
}
if(l <= s && r >= e){
search(st[i],k);
return ;
}
int mid = s + (e-s)/2;
query(s,mid,l,r,k,2*i+1);
query(mid+1,e,l,r,k,2*i+2);
}
static void search(Node root,int val){
if(root == null){
return ;
}
if(val < root.val){
count += (root.count+getCount(root.right));
search(root.left,val);
}else if(val > root.val){
search(root.right,val);
}else{
count += getCount(root.right);
}
}
static void updateST(int s,int e,int ind,int val,int i){
if(e < s){
return ;
}
if(ind < s || ind > e){
return ;
}
st[i] = delete(st[i],a[ind]);
st[i] = insert(st[i],val);
if(s == e){
return ;
}
int mid = s + (e-s)/2;
updateST(s,mid,ind,val,2*i+1);
updateST(mid+1,e,ind,val,2*i+2);
}
static Node delete(Node root,int val){
if(root == null){
return root;
}
if(val < root.val){
root.left = delete(root.left,val);
}else if(val > root.val){
root.right = delete(root.right,val);
}else{
if(root.count > 1){
root.count -= 1;
root.sum -= 1;
return root;
}else{
if(root.left == null){
return root.right;
}
if(root.right == null){
return root.left;
}
root.val = getSuc(root.right);
root.right = delete(root.right,root.val);
}
}
root.sum = root.count + getCount(root.left) + getCount(root.right);
return root;
}
static int getSuc(Node root){
int val = root.val;
while(root.left != null){
root = root.left;
val = root.val;
}
return val;
}
static void constructST(int s,int e,int i){
if(e < s){
return ;
}
if(e == s){
st[i] = insert(st[i],a[s]);
return ;
}
int mid = s + (e-s)/2;
constructST(s,mid,2*i+1);
constructST(mid+1,e,2*i+2);
for(int j=s;j<=e;j++){
st[i] = insert(st[i],a[j]);
}
}
static Node insert(Node root,int val){
if(root == null){
return new Node(val);
}
if(val == root.val){
root.count += 1;
root.sum += 1;
return root;
}else if(val < root.val){
root.left = insert(root.left,val);
}else if(val > root.val){
root.right = insert(root.right,val);
}
root.sum = getCount(root.left) + getCount(root.right) + root.count;
return root;
}
static int getCount(Node root){
if(root == null){
return 0;
}else{
return root.sum;
}
}
//For Fast I/O
private static class InputReader{
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
private SpaceCharFilter filter;
this.stream = stream;
}
public int read(){
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars){
curChar = 0;
try{
numChars = stream.read(buf);
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}
public int readInt(){
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-'){
sgn = -1;
c = read();
}
int res = 0;
do{
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do{
res.appendCodePoint(c);
c = read();
} while (!isSpaceChar(c));
return res.toString();
}
public boolean isSpaceChar(int c){
if (filter != null)
return filter.isSpaceChar(c);
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
return readString();
}
public interface SpaceCharFilter{
public boolean isSpaceChar(int ch);
}
}
private static class OutputWriter{
}
public OutputWriter
(Writer writer
){ }
public void print
(Object...
objects){ for (int i = 0; i < objects.length; i++){
if (i != 0)
writer.print(' ');
writer.print(objects[i]);
}
}
public void printLine
(Object...
objects) { print(objects);
writer.println();
}
public void close(){
writer.close();
}
public void flush(){
writer.flush();
}
}
}
aW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5pby4qOwpjbGFzcyBLUVVFUlkyewoJc3RhdGljIGNsYXNzIE5vZGV7CgkJaW50IHZhbDsKCQlOb2RlIGxlZnQ7CgkJTm9kZSByaWdodDsKCQlpbnQgY291bnQ7CgkJaW50IHN1bTsKCQlOb2RlKGludCB2YWwpewoJCQl0aGlzLnZhbCA9IHZhbDsKCQkJY291bnQgPSAxOwoJCQlzdW0gPSAxOwoJCQlsZWZ0ID0gbnVsbDsKCQkJcmlnaHQgPSBudWxsOwoJCX0KCX0KCXN0YXRpYyBpbnQgbiA7CglzdGF0aWMgaW50IFtdYTsKCXN0YXRpYyBOb2RlIFtdc3Q7CglzdGF0aWMgaW50IGNvdW50OwoJcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nIFtdYXJnKSB0aHJvd3MgSU9FeGNlcHRpb257CgkJSW5wdXRSZWFkZXIgaW4gPSBuZXcgSW5wdXRSZWFkZXIoU3lzdGVtLmluKTsKICAgICAgICBPdXRwdXRXcml0ZXIgb3V0ID0gbmV3IE91dHB1dFdyaXRlcihTeXN0ZW0ub3V0KTsKICAgICAgICBuID0gaW4ucmVhZEludCgpOwogICAgICAgIGEgPSBuZXcgaW50W25dOwogICAgICAgIGZvcihpbnQgaT0wO2k8bjtpKyspewogICAgICAgIAlhW2ldID0gaW4ucmVhZEludCgpOwogICAgICAgIH0KICAgICAgICBzdCA9IG5ldyBOb2RlWzQqbl07CiAgICAgICAgY29uc3RydWN0U1QoMCxuLTEsMCk7CiAgICAgICAgaW50IG0gPSBpbi5yZWFkSW50KCk7CiAgICAgICAgd2hpbGUobS0tID4wKXsKICAgICAgICAJaW50IGZsYWcgPSBpbi5yZWFkSW50KCk7CiAgICAgICAgCWlmKGZsYWcgPT0gMCl7CiAgICAgICAgCQlpbnQgaW5kID0gaW4ucmVhZEludCgpLTE7CiAgICAgICAgCQlpbnQgdmFsID0gaW4ucmVhZEludCgpOwogICAgICAgIAkJdXBkYXRlU1QoMCxuLTEsaW5kLHZhbCwwKTsKICAgICAgICAJfWVsc2V7CiAgICAgICAgCQlpbnQgbCA9IGluLnJlYWRJbnQoKS0xOwogICAgICAgIAkJaW50IHIgPSBpbi5yZWFkSW50KCktMTsKICAgICAgICAJCWludCBrID0gaW4ucmVhZEludCgpOwogICAgICAgIAkJY291bnQgPSAwOwogICAgICAgIAkJcXVlcnkoMCxuLTEsbCxyLGssMCk7CiAgICAgICAgCQlTeXN0ZW0ub3V0LnByaW50bG4oY291bnQpOwogICAgICAgIAl9CiAgICAgICAgfQoJfQogCglzdGF0aWMgdm9pZCBpbk9yZGVyKE5vZGUgcm9vdCl7CgkJaWYocm9vdCA9PSBudWxsKXsKCQkJcmV0dXJuIDsKCQl9CgkJaWYocm9vdC5sZWZ0ICE9IG51bGwpewoJCQlpbk9yZGVyKHJvb3QubGVmdCk7CgkJfQoJCVN5c3RlbS5vdXQucHJpbnQocm9vdC52YWwrIiAiKTsKCQlpZihyb290LnJpZ2h0ICE9IG51bGwpewoJCQlpbk9yZGVyKHJvb3QucmlnaHQpOwoJCX0KCX0KIAoJc3RhdGljIHZvaWQgcXVlcnkoaW50IHMsaW50IGUsaW50IGwsaW50IHIsaW50IGssaW50IGkpewoJCWlmKGwgPiBlIHx8IHIgPCBzKXsKCQkJcmV0dXJuIDsKCQl9CgkJaWYobCA8PSBzICYmIHIgPj0gZSl7CgkJCXNlYXJjaChzdFtpXSxrKTsKCQkJcmV0dXJuIDsKCQl9CgkJaW50IG1pZCA9IHMgKyAoZS1zKS8yOwoJCXF1ZXJ5KHMsbWlkLGwscixrLDIqaSsxKTsKCQlxdWVyeShtaWQrMSxlLGwscixrLDIqaSsyKTsKCX0KIAoJc3RhdGljIHZvaWQgc2VhcmNoKE5vZGUgcm9vdCxpbnQgdmFsKXsKCQlpZihyb290ID09IG51bGwpewoJCQlyZXR1cm4gOwoJCX0KCQlpZih2YWwgPCByb290LnZhbCl7CgkJCWNvdW50ICs9IChyb290LmNvdW50K2dldENvdW50KHJvb3QucmlnaHQpKTsKCQkJc2VhcmNoKHJvb3QubGVmdCx2YWwpOwoJCX1lbHNlIGlmKHZhbCA+IHJvb3QudmFsKXsKCQkJc2VhcmNoKHJvb3QucmlnaHQsdmFsKTsKCQl9ZWxzZXsKCQkJY291bnQgKz0gZ2V0Q291bnQocm9vdC5yaWdodCk7CgkJfQoJfQoKCXN0YXRpYyB2b2lkIHVwZGF0ZVNUKGludCBzLGludCBlLGludCBpbmQsaW50IHZhbCxpbnQgaSl7CgkJaWYoZSA8IHMpewoJCQlyZXR1cm4gOwoJCX0KCQlpZihpbmQgPCBzIHx8IGluZCA+IGUpewoJCQlyZXR1cm4gOwoJCX0KCQlzdFtpXSA9IGRlbGV0ZShzdFtpXSxhW2luZF0pOwoJCXN0W2ldID0gaW5zZXJ0KHN0W2ldLHZhbCk7CgkJaWYocyA9PSBlKXsKCQkJcmV0dXJuIDsKCQl9CgkJaW50IG1pZCA9IHMgKyAoZS1zKS8yOwoJCXVwZGF0ZVNUKHMsbWlkLGluZCx2YWwsMippKzEpOwoJCXVwZGF0ZVNUKG1pZCsxLGUsaW5kLHZhbCwyKmkrMik7Cgl9CiAKCXN0YXRpYyBOb2RlIGRlbGV0ZShOb2RlIHJvb3QsaW50IHZhbCl7CgkJaWYocm9vdCA9PSBudWxsKXsKCQkJcmV0dXJuIHJvb3Q7CgkJfQoJCWlmKHZhbCA8IHJvb3QudmFsKXsKCQkJcm9vdC5sZWZ0ID0gZGVsZXRlKHJvb3QubGVmdCx2YWwpOwoJCX1lbHNlIGlmKHZhbCA+IHJvb3QudmFsKXsKCQkJcm9vdC5yaWdodCA9IGRlbGV0ZShyb290LnJpZ2h0LHZhbCk7CgkJfWVsc2V7CgkJCWlmKHJvb3QuY291bnQgPiAxKXsKCQkJCXJvb3QuY291bnQgLT0gMTsKCQkJCXJvb3Quc3VtIC09IDE7CgkJCQlyZXR1cm4gcm9vdDsKCQkJfWVsc2V7CgkJCQlpZihyb290LmxlZnQgPT0gbnVsbCl7CgkJCQkJcmV0dXJuIHJvb3QucmlnaHQ7CgkJCQl9CgkJCQlpZihyb290LnJpZ2h0ID09IG51bGwpewoJCQkJCXJldHVybiByb290LmxlZnQ7CgkJCQl9CgkJCQlyb290LnZhbCA9IGdldFN1Yyhyb290LnJpZ2h0KTsKCQkJCXJvb3QucmlnaHQgPSBkZWxldGUocm9vdC5yaWdodCxyb290LnZhbCk7CgkJCX0KCQl9CgkJcm9vdC5zdW0gPSByb290LmNvdW50ICsgZ2V0Q291bnQocm9vdC5sZWZ0KSArIGdldENvdW50KHJvb3QucmlnaHQpOwoJCXJldHVybiByb290OwoJfQogCglzdGF0aWMgaW50IGdldFN1YyhOb2RlIHJvb3QpewoJCWludCB2YWwgPSByb290LnZhbDsKCQl3aGlsZShyb290LmxlZnQgIT0gbnVsbCl7CgkJCXJvb3QgPSByb290LmxlZnQ7CgkJCXZhbCA9IHJvb3QudmFsOwoJCX0KCQlyZXR1cm4gdmFsOwoJfQoKCXN0YXRpYyB2b2lkIGNvbnN0cnVjdFNUKGludCBzLGludCBlLGludCBpKXsKCQlpZihlIDwgcyl7CgkJCXJldHVybiA7CgkJfQoJCWlmKGUgPT0gcyl7CgkJCXN0W2ldID0gaW5zZXJ0KHN0W2ldLGFbc10pOwoJCQlyZXR1cm4gOwoJCX0KCQlpbnQgbWlkID0gcyArIChlLXMpLzI7CgkJY29uc3RydWN0U1QocyxtaWQsMippKzEpOwoJCWNvbnN0cnVjdFNUKG1pZCsxLGUsMippKzIpOwoJCWZvcihpbnQgaj1zO2o8PWU7aisrKXsKCQkJc3RbaV0gPSBpbnNlcnQoc3RbaV0sYVtqXSk7CgkJfQoJfQogCglzdGF0aWMgTm9kZSBpbnNlcnQoTm9kZSByb290LGludCB2YWwpewoJCWlmKHJvb3QgPT0gbnVsbCl7CgkJCXJldHVybiBuZXcgTm9kZSh2YWwpOwoJCX0KCQlpZih2YWwgPT0gcm9vdC52YWwpewoJCQlyb290LmNvdW50ICs9IDE7CgkJCXJvb3Quc3VtICs9IDE7CgkJCXJldHVybiByb290OwoJCX1lbHNlIGlmKHZhbCA8IHJvb3QudmFsKXsKCQkJcm9vdC5sZWZ0ID0gaW5zZXJ0KHJvb3QubGVmdCx2YWwpOwoJCX1lbHNlIGlmKHZhbCA+IHJvb3QudmFsKXsKCQkJcm9vdC5yaWdodCA9IGluc2VydChyb290LnJpZ2h0LHZhbCk7CgkJfQoJCXJvb3Quc3VtID0gZ2V0Q291bnQocm9vdC5sZWZ0KSArIGdldENvdW50KHJvb3QucmlnaHQpICsgcm9vdC5jb3VudDsKCQlyZXR1cm4gcm9vdDsKCX0KIAoJc3RhdGljIGludCBnZXRDb3VudChOb2RlIHJvb3QpewoJCWlmKHJvb3QgPT0gbnVsbCl7CgkJCXJldHVybiAwOwoJCX1lbHNlewoJCQlyZXR1cm4gcm9vdC5zdW07CgkJfQoJfQogCgkvL0ZvciBGYXN0IEkvTwoJcHJpdmF0ZSBzdGF0aWMgY2xhc3MgSW5wdXRSZWFkZXJ7CiAgICAgICAgcHJpdmF0ZSBJbnB1dFN0cmVhbSBzdHJlYW07CiAgICAgICAgcHJpdmF0ZSBieXRlW10gYnVmID0gbmV3IGJ5dGVbMTAyNF07CiAgICAgICAgcHJpdmF0ZSBpbnQgY3VyQ2hhcjsKICAgICAgICBwcml2YXRlIGludCBudW1DaGFyczsKICAgICAgICBwcml2YXRlIFNwYWNlQ2hhckZpbHRlciBmaWx0ZXI7CiAKICAgICAgICBwdWJsaWMgSW5wdXRSZWFkZXIoSW5wdXRTdHJlYW0gc3RyZWFtKXsKICAgICAgICAgICAgdGhpcy5zdHJlYW0gPSBzdHJlYW07CiAgICAgICAgfQogCiAgICAgICAgcHVibGljIGludCByZWFkKCl7CiAgICAgICAgICAgIGlmIChudW1DaGFycyA9PSAtMSkKICAgICAgICAgICAgICAgIHRocm93IG5ldyBJbnB1dE1pc21hdGNoRXhjZXB0aW9uKCk7CiAgICAgICAgICAgIGlmIChjdXJDaGFyID49IG51bUNoYXJzKXsKICAgICAgICAgICAgICAgIGN1ckNoYXIgPSAwOwogICAgICAgICAgICAgICAgdHJ5ewogICAgICAgICAgICAgICAgICAgIG51bUNoYXJzID0gc3RyZWFtLnJlYWQoYnVmKTsKICAgICAgICAgICAgICAgIH0gY2F0Y2ggKElPRXhjZXB0aW9uIGUpewogICAgICAgICAgICAgICAgICAgIHRocm93IG5ldyBJbnB1dE1pc21hdGNoRXhjZXB0aW9uKCk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBpZiAobnVtQ2hhcnMgPD0gMCkKICAgICAgICAgICAgICAgICAgICByZXR1cm4gLTE7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgcmV0dXJuIGJ1ZltjdXJDaGFyKytdOwogICAgICAgIH0KIAogICAgICAgIHB1YmxpYyBpbnQgcmVhZEludCgpewogICAgICAgICAgICBpbnQgYyA9IHJlYWQoKTsKICAgICAgICAgICAgd2hpbGUgKGlzU3BhY2VDaGFyKGMpKQogICAgICAgICAgICAgICAgYyA9IHJlYWQoKTsKICAgICAgICAgICAgaW50IHNnbiA9IDE7CiAgICAgICAgICAgIGlmIChjID09ICctJyl7CiAgICAgICAgICAgICAgICBzZ24gPSAtMTsKICAgICAgICAgICAgICAgIGMgPSByZWFkKCk7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgaW50IHJlcyA9IDA7CiAgICAgICAgICAgIGRvewogICAgICAgICAgICAgICAgaWYgKGMgPCAnMCcgfHwgYyA+ICc5JykKICAgICAgICAgICAgICAgICAgICB0aHJvdyBuZXcgSW5wdXRNaXNtYXRjaEV4Y2VwdGlvbigpOwogICAgICAgICAgICAgICAgcmVzICo9IDEwOwogICAgICAgICAgICAgICAgcmVzICs9IGMgLSAnMCc7CiAgICAgICAgICAgICAgICBjID0gcmVhZCgpOwogICAgICAgICAgICB9IHdoaWxlICghaXNTcGFjZUNoYXIoYykpOwogICAgICAgICAgICByZXR1cm4gcmVzICogc2duOwogICAgICAgIH0KIAogICAgICAgIHB1YmxpYyBTdHJpbmcgcmVhZFN0cmluZygpewogICAgICAgICAgICBpbnQgYyA9IHJlYWQoKTsKICAgICAgICAgICAgd2hpbGUgKGlzU3BhY2VDaGFyKGMpKQogICAgICAgICAgICAgICAgYyA9IHJlYWQoKTsKICAgICAgICAgICAgU3RyaW5nQnVpbGRlciByZXMgPSBuZXcgU3RyaW5nQnVpbGRlcigpOwogICAgICAgICAgICBkb3sKICAgICAgICAgICAgICAgIHJlcy5hcHBlbmRDb2RlUG9pbnQoYyk7CiAgICAgICAgICAgICAgICBjID0gcmVhZCgpOwogICAgICAgICAgICB9IHdoaWxlICghaXNTcGFjZUNoYXIoYykpOwogICAgICAgICAgICByZXR1cm4gcmVzLnRvU3RyaW5nKCk7CiAgICAgICAgfQogCiAgICAgICAgcHVibGljIGJvb2xlYW4gaXNTcGFjZUNoYXIoaW50IGMpewogICAgICAgICAgICBpZiAoZmlsdGVyICE9IG51bGwpCiAgICAgICAgICAgICAgICByZXR1cm4gZmlsdGVyLmlzU3BhY2VDaGFyKGMpOwogICAgICAgICAgICByZXR1cm4gYyA9PSAnICcgfHwgYyA9PSAnXG4nIHx8IGMgPT0gJ1xyJyB8fCBjID09ICdcdCcgfHwgYyA9PSAtMTsKICAgICAgICB9CiAKICAgICAgICBwdWJsaWMgU3RyaW5nIG5leHQoKXsKICAgICAgICAgICAgcmV0dXJuIHJlYWRTdHJpbmcoKTsKICAgICAgICB9CiAKICAgICAgICBwdWJsaWMgaW50ZXJmYWNlIFNwYWNlQ2hhckZpbHRlcnsKICAgICAgICAgICAgcHVibGljIGJvb2xlYW4gaXNTcGFjZUNoYXIoaW50IGNoKTsKICAgICAgICB9CiAgICB9CiAKICAgIHByaXZhdGUgc3RhdGljIGNsYXNzIE91dHB1dFdyaXRlcnsKICAgICAgICBwcml2YXRlIGZpbmFsIFByaW50V3JpdGVyIHdyaXRlcjsKIAogICAgICAgIHB1YmxpYyBPdXRwdXRXcml0ZXIoT3V0cHV0U3RyZWFtIG91dHB1dFN0cmVhbSl7CiAgICAgICAgICAgIHdyaXRlciA9IG5ldyBQcmludFdyaXRlcihuZXcgQnVmZmVyZWRXcml0ZXIobmV3IE91dHB1dFN0cmVhbVdyaXRlcihvdXRwdXRTdHJlYW0pKSk7CiAgICAgICAgfQogCiAgICAgICAgcHVibGljIE91dHB1dFdyaXRlcihXcml0ZXIgd3JpdGVyKXsKICAgICAgICAgICAgdGhpcy53cml0ZXIgPSBuZXcgUHJpbnRXcml0ZXIod3JpdGVyKTsKICAgICAgICB9CiAKICAgICAgICBwdWJsaWMgdm9pZCBwcmludChPYmplY3QuLi4gb2JqZWN0cyl7CiAgICAgICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgb2JqZWN0cy5sZW5ndGg7IGkrKyl7CiAgICAgICAgICAgICAgICBpZiAoaSAhPSAwKQogICAgICAgICAgICAgICAgICAgIHdyaXRlci5wcmludCgnICcpOwogICAgICAgICAgICAgICAgd3JpdGVyLnByaW50KG9iamVjdHNbaV0pOwogICAgICAgICAgICB9CiAgICAgICAgfQogCiAgICAgICAgcHVibGljIHZvaWQgcHJpbnRMaW5lKE9iamVjdC4uLiBvYmplY3RzKSB7CiAgICAgICAgICAgIHByaW50KG9iamVjdHMpOwogICAgICAgICAgICB3cml0ZXIucHJpbnRsbigpOwogICAgICAgIH0KIAogICAgICAgIHB1YmxpYyB2b2lkIGNsb3NlKCl7CiAgICAgICAgICAgIHdyaXRlci5jbG9zZSgpOwogICAgICAgIH0KIAogICAgICAgIHB1YmxpYyB2b2lkIGZsdXNoKCl7CiAgICAgICAgICAgIHdyaXRlci5mbHVzaCgpOwogICAgICAgIH0KICAgIH0KfSAK