#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
int n,m,a[1000010];
int find1(int l,int r){
	int b[100010];
	memset(b,0x3f,sizeof b);
	int ans=r-l+1;
	for(int i=l;i<=r;i++){
		*upper_bound(b+1,b+1+ans,a[i])=a[i];
	}
	int sum=lower_bound(b+1,b+ans+1,INF)-b-1;
	return sum;
}
int find2(int l,int r){
	int b[10001];
	int ans=r-l+1;
	memset(b,0x3f,sizeof b);
	for(int i=l;i<=r;i++){
		*lower_bound(b+1,b+ans+1,a[i])=a[i];
	}
	int sum=lower_bound(b+1,b+ans+1,INF)-b-1;
	return sum;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	while(m--){
		int a1,a2,a3;
		cin>>a1>>a2>>a3;
		if(a1==1){
			cout<<find1(a2,a3)<<endl;
		}else{
			cout<<find2(a2,a3)<<endl;
		}
	}
	return 0;
}

感觉写的很怪又找不出来问题，大佬指点一下我呗