#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define debug(...) fprintf(stderr,__VA_ARGS__)
#else
#define debug(...)
#endif
using namespace std;
using namespace chrono;
typedef signed char i8;typedef short i16;typedef int i32;typedef long long i64;typedef unsigned char u8;typedef unsigned short u16;typedef unsigned u32;typedef unsigned long long u64;typedef float f32;typedef double f64;typedef long double f96;
template<typename A,typename B>void to_max(A& a,B b){if(a<b)a=b;}
template<typename A,typename B>void to_min(A& a,B b){if(b<a)a=b;}
namespace fast_io{
#ifndef __cplusplus
#define __cplusplus 201402L
#endif
const unsigned is(1<<21),os(1<<14);bool ne;char i[is],o[os],*ib(i),*ie(i),*ob(o),*oe(o+os),a[20],&c(*a),*b;void f(){ob-=fwrite(o,1,ob-o,stdout);}void p(char c){if(ob==oe)f();*ob++=c;}template<typename T>void _write(T&r){if(r==0)return p('0');if(r<0)p('-'),r=~(r-1);for(b=a;r;r/=10)*++b=(r%10)^'0';while(b!=a)p(*b--);}
#define g (ib==ie&&(ie=(ib=i)+fread(i,1,is,stdin),ib==ie)?-1:*ib++)
void reads(char*s){for(c=g;~c&&isspace(c);c=g);for(*s++=c,c=g;~c&&!isspace(c);c=g)*s++=c;*s=0;}template<typename T>void read(T&r){ne=false;for(c=g;~c&&(c<'0'||c>'9');c=g)ne=(c=='-');for(r=c^'0',c=g;isdigit(c);c=g)r=(r<<3)+(r<<1)+(c^'0');if(ne)r=~(r-1);}template<>void read<char>(char&r){for(c=g;~c&&isspace(c);c=g);r=c;}template<>void read<string>(string&r){r.clear();for(c=g;~c&&isspace(c);c=g);for(r.push_back(c),c=g;~c&&!isspace(c);c=g)r.push_back(c);}
#undef g
#if(__cplusplus>=201703L)
template<typename...Args>void read(Args&...args){(read(args),...);}template<typename...Args>void _write(Args&...args){(_write(args),...);}
#else
template<typename T,typename...args>void read(T&a,args&...b){read(a);read(b...);}template<typename T,typename...args>void _write(T&a,args&...b){_write(a);_write(b...);}
#endif
template<>void _write<char>(char&r){p(r);}template<>void _write<char*>(char*&r){for(;*r;p(*r++));}template<>void _write<const char*>(const char*&r){for(;*r;p(*r++));}template<>void _write<string>(string&r){const char*s(r.data());_write(s);}template<typename...args>void write(args...a){_write(a...);}struct _des{~_des(){f();}}d;}using fast_io::read;using fast_io::reads;using fast_io::write;

constexpr int N(1e6+5);
i8 log_2[N];
int n,m,s[N][2],st[19][N];

int query(int l,int r){
	i8 k(log_2[r-l+1]);
	return max(st[k][l],st[k][r-(1<<k)+1]);
}
int main(){
	i8 a;
	int i,j,l,r;
	read(n,m);
	for(i=1;i<=n;++i){
		read(a);
		s[i][0]=s[i-1][0];
		s[i][1]=s[i-1][1];
		++s[i][a];
		log_2[i+1]=log_2[(i+1)>>1]+1;
	}
	for(i=0;i<=n;++i){
		st[0][i]=s[i][0]+s[n][1]-s[i][1];
	}
	for(i=1;i<20;++i){
		for(j=0;j<=n-(1<<(i-1));++j){
			st[i][j]=max(st[i-1][j],st[i-1][j+(1<<(i-1))]);
		}
	}
	for(i=1;i<=m;++i){
		read(a,l,r);
		if(a==1){
			write(query(l-1,r)-s[l-1][0]-(s[n][1]-s[r][1]),'\n');
		}else{
			j=s[r][1]-s[l-1][1];
			if(j==0||j==r-l+1||s[l+j-1][1]-s[l-1][1]==j){
				write("1\n");
			}else{
				write("2\n");
			}
		}
	}
	return 0;
}