记录

#14 15 死活过不去，能卡常的都卡了。

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 17;

int n, m, a[N], L[N], R[N], pre[N], lst[N], st[22][N], mx[22][N];

namespace IO{
	int len=0;
	char ibuf[(1<<20)+1],*iS,*iT,out[(1<<26)+1];
	#define gh() (iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<20)+1,stdin),(iS==iT?EOF:*iS++):*iS++)
	#define reg register
	inline int read(){
		reg char ch=gh();
		reg int x=0;
		reg char t=0;
		while(ch<'0'||ch>'9')   t|=ch=='-',ch=gh();
		while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();
		return t?-x:x;
	}
	inline void putc(char ch){
		out[len++]=ch;
	}
	template<class T>
	inline void write(T x){
		if(x<0)putc('-'),x=-x;
		if(x>9)write(x/10);
		out[len++]=x%10+48;
	}
	inline void flush(){
		fwrite(out,1,len,stdout);
		len=0;
	}
}
using IO::read;
using IO::write;
using IO::flush;
using IO::putc;

void qmax(int &x, int y) {
	if(y > x) x = y;
}

signed main() {
	n = read(); m = read();
	for(int i = 1; i <= n; i++) 
		a[i] = read();
	int tag = 0;
	for(int i = 1; i <= n; i++) {
		if(a[i] == 1) {
			tag = i;
		}
		L[i] = tag;
		pre[i] = pre[i - 1];
		if(a[i] == 0) pre[i] ++;
	}
	tag = n + 1;
	for(int i = n; i > 0; i--) {
		if(a[i] == 0) {
			tag = i;
		}
		R[i] = tag; 
		lst[i] = lst[i + 1];
		if(a[i] == 1) lst[i] ++;
	}
//	for(int i = 1; i <= n; i++) {
//		printf("%d %d\n", pre[i], lst[i]);
//	}
	for(int i = 1; i <= n; i++)
		st[0][i] = i + 1, mx[0][i] = lst[i + 1] + pre[i + 1]; 
	st[0][n + 1] = n + 1;
	for(int lg = 1; lg < 20; lg ++) {
		for(int i = 1; i <= n + 1; i++) {
			st[lg][i] = st[lg - 1][st[lg - 1][i]];
			mx[lg][i] = max(mx[lg - 1][i], mx[lg - 1][st[lg - 1][i]]); // ?
		}
	}
//	printf("114514");
//	for(int lg = 1; lg < 20; lg ++) {
//		for(int i = 1; i <= n; i++) {
//			printf("%d ", st[lg][i]); 
//		}
//		printf("\n");
//	} 
//	printf("%d %d\n", st[1][3], mx[1][3]);

	while(m --) {
		int opt, l, r;
		opt = read(); l = read(); r = read();
		if(opt == 1) {
			int y = 0, u = l, res = pre[u] + lst[u], delt = r - l;
			while(delt) {
				if(delt & 1) qmax(res, mx[y][u]), u = st[y][u]; 
				delt >>= 1, y++;
			}
			write(res - pre[l - 1] - lst[r + 1]);
			putc('\n');
		}
		else {
			if(L[r] > R[l]) write(2);
			else write(1);
			putc('\n');
		}
	}
	flush();
	return 0;
}