#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
const int B = 1005;
using pi = pair<int, int>;
int n, q, a[MAXN];
int nxt[MAXN];
struct query{ int t, x, y, z; };
bool upd[MAXN];
void Batch(vector<query> &Q){
vector<int> v;
int idx = 0;
for(auto &i : Q){
if(i.t == 1){
v.push_back(i.x);
v.push_back(i.x + 1);
upd[i.x] = 1;
}
else{
v.push_back(i.x);
v.push_back(i.y);
}
idx++;
}
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end()) - v.begin());
for(int i=0; i<v.size()-1; i++){
if(upd[v[i]]){
for(auto &j : Q){
if(j.t == 1){
if(j.x == v[i]){
a[j.x] = j.y;
}
continue;
}
if(j.x <= v[i] && j.y >= v[i] + 1 && j.z == a[v[i]]){
j.z++;
}
}
upd[v[i]] = 0;
}
else{
for(int j=v[i+1]-1; j>=v[i]; j--){
nxt[a[j]] = nxt[a[j] + 1] + 1;
}
for(auto &j : Q){
if(j.t == 2 && j.x <= v[i] && j.y >= v[i+1]){
j.z += nxt[j.z];
}
}
for(int j=v[i]; j<v[i+1]; j++) nxt[a[j]] = 0;
}
}
for(auto &i : Q){
if(i.t == 2) printf("%d\n", i.z - 1);
}
Q.clear();
}
namespace FIO{
static char buf[1<<19];
static int idx = 0;
static int bytes = 0;
static inline int _read(){
if(!bytes || idx == bytes){
bytes = (int)fread(buf, sizeof(buf[0]), sizeof(buf), stdin);
idx = 0;
}
return buf[idx++];
}
static inline int _readInt(){
int x = 0, s = 1;
int c = _read();
while(c <= 32) c = _read();
if(c == '-') s = -1, c = _read();
while(c > 32){
x = 10 * x + (c - '0');
c = _read();
}
if(s < 0) x = -x;
return x;
}
}
int main(){
vector<query> qry;
n = FIO::_readInt();
q = FIO::_readInt();
for(int i=0; i<n; i++){
a[i] = FIO::_readInt();
}
while(q--){
int t = FIO::_readInt();
if(t == 1){
int x, y;
x = FIO::_readInt();
y = FIO::_readInt();
qry.push_back({1, x, y});
}
else{
int l, r, k;
l = FIO::_readInt();
r = FIO::_readInt();
k = FIO::_readInt();
qry.push_back({2, l, r, k});
}
if(qry.size() > B){
Batch(qry);
}
}
Batch(qry);
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmNvbnN0IGludCBNQVhOID0gMTAwMDAwNTsKY29uc3QgaW50IEIgPSAxMDA1Owp1c2luZyBwaSA9IHBhaXI8aW50LCBpbnQ+OwoKaW50IG4sIHEsIGFbTUFYTl07CgppbnQgbnh0W01BWE5dOwoKc3RydWN0IHF1ZXJ5eyBpbnQgdCwgeCwgeSwgejsgfTsKYm9vbCB1cGRbTUFYTl07Cgp2b2lkIEJhdGNoKHZlY3RvcjxxdWVyeT4gJlEpewoJdmVjdG9yPGludD4gdjsKCWludCBpZHggPSAwOwoJZm9yKGF1dG8gJmkgOiBRKXsKCQlpZihpLnQgPT0gMSl7CgkJCXYucHVzaF9iYWNrKGkueCk7CgkJCXYucHVzaF9iYWNrKGkueCArIDEpOwoJCQl1cGRbaS54XSA9IDE7CgkJfQoJCWVsc2V7CgkJCXYucHVzaF9iYWNrKGkueCk7CgkJCXYucHVzaF9iYWNrKGkueSk7CgkJfQoJCWlkeCsrOwoJfQoJc29ydCh2LmJlZ2luKCksIHYuZW5kKCkpOwoJdi5yZXNpemUodW5pcXVlKHYuYmVnaW4oKSwgdi5lbmQoKSkgLSB2LmJlZ2luKCkpOwoJZm9yKGludCBpPTA7IGk8di5zaXplKCktMTsgaSsrKXsKCQlpZih1cGRbdltpXV0pewoJCQlmb3IoYXV0byAmaiA6IFEpewoJCQkJaWYoai50ID09IDEpewoJCQkJCWlmKGoueCA9PSB2W2ldKXsKCQkJCQkJYVtqLnhdID0gai55OwoJCQkJCX0KCQkJCQljb250aW51ZTsKCQkJCX0KCQkJCWlmKGoueCA8PSB2W2ldICYmIGoueSA+PSB2W2ldICsgMSAmJiBqLnogPT0gYVt2W2ldXSl7CgkJCQkJai56Kys7CgkJCQl9CgkJCX0KCQkJdXBkW3ZbaV1dID0gMDsKCQl9CgkJZWxzZXsKCQkJZm9yKGludCBqPXZbaSsxXS0xOyBqPj12W2ldOyBqLS0pewoJCQkJbnh0W2Fbal1dID0gbnh0W2Fbal0gKyAxXSArIDE7CgkJCX0KCQkJZm9yKGF1dG8gJmogOiBRKXsKCQkJCWlmKGoudCA9PSAyICYmIGoueCA8PSB2W2ldICYmIGoueSA+PSB2W2krMV0pewoJCQkJCWoueiArPSBueHRbai56XTsKCQkJCX0KCQkJfQoJCQlmb3IoaW50IGo9dltpXTsgajx2W2krMV07IGorKykgbnh0W2Fbal1dID0gMDsKCQl9Cgl9Cglmb3IoYXV0byAmaSA6IFEpewoJCWlmKGkudCA9PSAyKSBwcmludGYoIiVkXG4iLCBpLnogLSAxKTsKCX0KCVEuY2xlYXIoKTsKfQoKbmFtZXNwYWNlIEZJT3sKCXN0YXRpYyBjaGFyIGJ1ZlsxPDwxOV07CglzdGF0aWMgaW50IGlkeCA9IDA7CglzdGF0aWMgaW50IGJ5dGVzID0gMDsKCXN0YXRpYyBpbmxpbmUgaW50IF9yZWFkKCl7CgkJaWYoIWJ5dGVzIHx8IGlkeCA9PSBieXRlcyl7CgkJCWJ5dGVzID0gKGludClmcmVhZChidWYsIHNpemVvZihidWZbMF0pLCBzaXplb2YoYnVmKSwgc3RkaW4pOwoJCQlpZHggPSAwOwoJCX0KCQlyZXR1cm4gYnVmW2lkeCsrXTsKCX0KCXN0YXRpYyBpbmxpbmUgaW50IF9yZWFkSW50KCl7CgkJaW50IHggPSAwLCBzID0gMTsKCQlpbnQgYyA9IF9yZWFkKCk7CgkJd2hpbGUoYyA8PSAzMikgYyA9IF9yZWFkKCk7CgkJaWYoYyA9PSAnLScpIHMgPSAtMSwgYyA9IF9yZWFkKCk7CgkJd2hpbGUoYyA+IDMyKXsKCQkJeCA9IDEwICogeCArIChjIC0gJzAnKTsKCQkJYyA9IF9yZWFkKCk7CgkJfQoJCWlmKHMgPCAwKSB4ID0gLXg7CgkJcmV0dXJuIHg7Cgl9Cn0KCmludCBtYWluKCl7Cgl2ZWN0b3I8cXVlcnk+IHFyeTsKCW4gPSBGSU86Ol9yZWFkSW50KCk7CglxID0gRklPOjpfcmVhZEludCgpOwoJZm9yKGludCBpPTA7IGk8bjsgaSsrKXsKCQlhW2ldID0gRklPOjpfcmVhZEludCgpOwoJfQoJd2hpbGUocS0tKXsKCQlpbnQgdCA9IEZJTzo6X3JlYWRJbnQoKTsKCQlpZih0ID09IDEpewoJCQlpbnQgeCwgeTsKCQkJeCA9IEZJTzo6X3JlYWRJbnQoKTsKCQkJeSA9IEZJTzo6X3JlYWRJbnQoKTsKCQkJcXJ5LnB1c2hfYmFjayh7MSwgeCwgeX0pOwoJCX0KCQllbHNlewoJCQlpbnQgbCwgciwgazsKCQkJbCA9IEZJTzo6X3JlYWRJbnQoKTsKCQkJciA9IEZJTzo6X3JlYWRJbnQoKTsKCQkJayA9IEZJTzo6X3JlYWRJbnQoKTsKCQkJcXJ5LnB1c2hfYmFjayh7MiwgbCwgciwga30pOwoJCX0KCQlpZihxcnkuc2l6ZSgpID4gQil7CgkJCUJhdGNoKHFyeSk7CgkJfQoJfQoJQmF0Y2gocXJ5KTsKfQ==