#include <bits/stdc++.h>
#define fr first
#define sc second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define endl '\n'
#define pw(x) (1ll << x)
#define sz(x) (int)((x).size())
#define sqr(x) ((ll)x)*((ll)x)
#define bcnt(X) __builtin_popcountll(X)
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
const int N = 1e6 + 10;
int fnw[N];
inline void upd (int pos, int x) { pos += 5;
for (; pos < N; pos += (pos & (-pos))) fnw[pos] += x;
}
inline void upd (int l, int r, int x) {
if (l > r) swap(l, r);
upd(l, x);
upd(r + 1, -x);
}
inline int get (int x) { x += 5;
int ret = 0;
for (; x; x -= (x & (-x))) ret += fnw[x];
return ret;
}
signed main ()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, q; cin >> n >> q;
vector <int> h (n);
for (auto &i : h) cin >> i;
for (int i = 1; i < n; i++) {
upd(h[i - 1], h[i], 1);
}
if (n == 1) {
while (q--) {
int tp; cin >> tp;
if (tp == 1) {
int i, x; cin >> i >> x;
h[0] = x;
}
else {
int y; cin >> y;
cout << (y == h[0]) << endl;
}
}
return 0;
}
while (q--) {
int tp; cin >> tp;
if (tp == 1) {
int i, x; cin >> i >> x;
i--;
if (i == 0) {
upd(h[0], h[1], -1);
h[0] = x;
upd(h[0], h[1], 1);
}
else if (i == n - 1) {
upd(h[n - 2], h[n - 1], -1);
h[n - 1] = x;
upd(h[n - 2], h[n - 1], 1);
}
else {
upd(h[i], h[i + 1], -1);
upd(h[i - 1], h[i], -1);
h[i] = x;
upd(h[i], h[i + 1], 1);
upd(h[i - 1], h[i], 1);
}
}
else {
int y; cin >> y;
cout << get(y) << endl;
}
}
return 0;
}
