#include <iostream>
#include <algorithm>
using namespace std;
typedef pair < int, int > PII;
typedef pair < int, PII > Type;
const int NMAX = 2e5 + 1, QMAX = 2e5 + 1;
int N, Q, A[NMAX];
Type Queries[QMAX];
int B[(NMAX + QMAX)], V[(NMAX + QMAX)];
static inline void Read ()
{
ios_base :: sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> Q;
for(int i = 1; i <= N; ++i)
cin >> A[i], B[++B[0]] = A[i];
for(int i = 1; i <= Q; ++i)
{
cin >> Queries[i].first >> Queries[i].second.first;
if(Queries[i].first == 2)
cin >> Queries[i].second.second, B[++B[0]] = Queries[i].second.second;
else
B[++B[0]] = Queries[i].second.first;
}
return;
}
static inline int Find (int Val)
{
return (int)(lower_bound(V + 1, V + V[0] + 1, Val) - V);
}
static inline void Replace ()
{
for(int i = 1; i <= N; ++i)
A[i] = Find(A[i]);
for(int i = 1; i <= Q; ++i)
if(Queries[i].first == 1)
Queries[i].second.first = Find(Queries[i].second.first);
else
Queries[i].second.second = Find(Queries[i].second.second);
return;
}
static inline void Normalize ()
{
sort(B + 1, B + B[0] + 1);
V[++V[0]] = B[1];
for(int i = 2; i <= B[0]; ++i)
if(B[i] != B[i - 1])
V[++V[0]] = B[i];
Replace();
return;
}
class SegmentTree
{
static const int NMAX = (4e5 + 1);
int A[(NMAX << 2)], Lazy[(NMAX << 2)];
private:
inline void Go (int Node, int a, int b)
{
if(a == b)
return;
if(Lazy[Node] == 0)
return;
int Mid = ((a + b) >> 1);
A[(Node << 1)] += Lazy[Node] * (Mid - a + 1), Lazy[(Node << 1)] += Lazy[Node];
A[((Node << 1) + 1)] += Lazy[Node] * (b - Mid), Lazy[((Node << 1) + 1)] += Lazy[Node];
Lazy[Node] = 0;
return;
}
public:
inline void Update (int Node, int a, int b, int ua, int ub, int Val)
{
if(ua <= a && b <= ub)
{
Lazy[Node] += Val;
A[Node] += Val * (b - a + 1);
return;
}
Go(Node, a, b);
int Mid = ((a + b) >> 1);
if(ua <= Mid)
Update((Node << 1), a, Mid, ua, ub, Val);
if(ub > Mid)
Update(((Node << 1) + 1), Mid + 1, b, ua, ub, Val);
A[Node] = A[(Node << 1)] + A[((Node << 1) + 1)];
return;
}
inline int Query (int Node, int a, int b, int qa, int qb)
{
if(qa <= a && b <= qb)
return A[Node];
Go(Node, a, b);
int Mid = ((a + b) >> 1);
int p_Left = 0, p_Right = 0;
if(qa <= Mid)
p_Left = Query((Node << 1), a, Mid, qa, qb);
if(qb > Mid)
p_Right = Query(((Node << 1) + 1), Mid + 1, b, qa, qb);
return (p_Left + p_Right);
}
} AINT;
static inline void Initialize ()
{
for(int i = 1; i <= N; ++i)
if(A[i] > A[i - 1])
AINT.Update(1, 1, V[0], A[i - 1] + 1, A[i], 1);
return;
}
static inline void Solve ()
{
Initialize();
for(int i = 1; i <= Q; ++i)
if(Queries[i].first == 1)
cout << AINT.Query(1, 1, V[0], Queries[i].second.first, Queries[i].second.first) << '\n';
else
{
int pos = Queries[i].second.first, X = Queries[i].second.second;
if(A[pos] > A[pos - 1])
AINT.Update(1, 1, V[0], A[pos - 1] + 1, A[pos], -1);
if(A[pos] < A[pos + 1])
AINT.Update(1, 1, V[0], A[pos] + 1, A[pos + 1], -1);
A[pos] = X;
if(A[pos] > A[pos - 1])
AINT.Update(1, 1, V[0], A[pos - 1] + 1, A[pos], 1);
if(A[pos] < A[pos + 1])
AINT.Update(1, 1, V[0], A[pos] + 1, A[pos + 1], 1);
A[pos] = X;
}
return;
}
int main()
{
Read();
Normalize();
Solve();
return 0;
}
