There is a array contain N(1<N<=100000) numbers. Now give you M(1<M<10000) query.

Every query will be:

1 x : ask longest substring which every number no less than x

2 y x : change the A[y] to x. there are at most change 10 times.

For each ask can you tell me the length of longest substring.

There are multiple tests.

each test first line contain two integer numbers N M,second line contain N integer numbers.

Next M lines each line will be:

1 x : ask longest substring which every number no less than x

2 y x : change the A[y] to x. there are at most change 10 times.

0 < N <= 100000, 0 < M <= 10000, -1000000000 <= A[i] <= 1000000000

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

const int INF = 1e9;

const double eps = 1e-;

const int N = ;

int cas = ;

struct _node{

    int pos,val,ans;

    friend bool operator < (const _node &a, const _node &b)

    {

        return a.val < b.val;

    }

};

int n,m;

int fa[N],sum[N],b[N],mxval;

_node a[N];

int find(int x)

{

    return fa[x]==x?x:fa[x]=find(fa[x]);

}

void un(int u,int v)

{

    u=find(u), v=find(v);

    fa[u]=v;

    sum[v]+=sum[u];

}

void pre()

{

    memset(sum,,sizeof(sum));

    mxval = -INF-;

    for(int i=;i<n;i++) fa[i]=i;

    for(int i=;i<n;i++)

    {

        a[i].val=b[i],a[i].pos=i;

        if(a[i].val > mxval) mxval = a[i].val;

    }

    sort(a,a+n);

    int mx = ;

    for(int i=n-;i>=;i--)

    {

        sum[a[i].pos]=;

        if(sum[a[i].pos-]) un(a[i].pos-,a[i].pos);

        if(sum[a[i].pos+]) un(a[i].pos+,a[i].pos);

        if(mx < sum[find(a[i].pos)]) mx = sum[fa[a[i].pos]];

        a[i].ans = mx;

    }

}

int solve(int x)

{

    _node t;

    t.val=x;

    int id = lower_bound(a,a+n,t) - a;

    return a[id].ans;

}

void run()

{

    for(int i=;i<n;i++)

        scanf("%d",b+i);

    pre();

    int x,y,op;

    while(m--)

    {

        scanf("%d",&op);

        if(op==)

        {

            scanf("%d",&x);

            if(x>mxval) puts("");

            else printf("%d\n",solve(x));

        }

        else

        {

            scanf("%d%d",&y,&x);

            b[y-]=x;

            pre();

        }

    }

}

int main()

{

    #ifdef LOCAL

    freopen("case.txt","r",stdin);

    #endif

    while(scanf("%d%d",&n,&m)!=EOF)

        run();

    return ;

}