注意力惊人的注意到答案 $\le 3$，证明考虑在原序列上或在取反序列上找到前缀和序列的最大最小值，然后向前向后各跑一次即可。

考虑继续挖掘性质。$ans=0/1$ 情况显然，不过 $ans=1$ 启示我们最后一次 $2/3$ 操作一定可以是全局操作。

若 $ans=2$，要么是因为可以通过取反转化成一个 $ans=1$ 的情况，要么是因为可以通过一次 $2/3$ 操作转化为一个可以只做一次全局 $2/3$ 操作的情况。若 $ans=3$，就是可以通过一次取反转化为刚才所说的 $ans=2$ 的第二种情况。

难点在于 $ans=2$ 的第二种情况，考虑不妨设全局操作做 $2$ 操作，对第一次操作类型进行分讨：

1. 第一次操作类型为 $2$。那么我们容易发现第一次操作前缀一定不劣，然后暴力找到第一个前缀和 $<0$ 的地方，尝试对这个区间进行一次操作，看看能否转化成一个可用一次全局 $2$ 解决的情况。

2. 第一次操作类型为 $3$。设操作区间为 $[l,r]$，前缀和数组为 $sum_i$，后缀和数组为 $ds_i$。考虑右移右端点，查找最优左端点，则有：

   1. $$\min\limits_{i=1}^{l-1}sum_i\ge 0$$ 直接找出 $pos$ 满足 $\min\limits_{i=1}^{pos-1}sum_i\ge 0$ 且 $sum_{pos}<0$，该性质就可以转化为 $l\le pos$。
   2. $$(l-1)sum_r+S_l\le\min\limits_{i=l}^r(isum_r+S_i)$$ 这个式子的来源是由于第一次操作后 $[l,r]$ 内的每个数都会变成 $sum_{r}-sum_{i-1}$，则前缀和变为：$$sum_{l-1}+\sum\limits_{i=l}^i(sum_r-sum_{i-1})$$ $$=(i-l+1)sum_r+S_l-S_i\ge 0$$ 移项即可得到上述式子。 设 $f_i(r)=isum_r+S_i$，则上式可表示为：$$f_l(r)-sum_r\le\min\limits_{i=l}^r f_i(r)$$ 显然不好处理，考虑按 $pos$ 划分，则有：$$f_l(r)-sum_r\le\min(\min\limits_{i=l}^{pos}f_i(r),\min\limits_{i=pos}^rf_i(r))$$显然左式取 $l=\operatorname{argmin}\limits_{i=1}^{pos} f_i(r)$ 时一定小于右侧前半部分，同时一定是对于右侧后半部分的最小解，所以只需 $check$ 这个位置即可。
   3. $$(l-1)sum_r+S_l\le rsum_r+S_{r+1}+\min_{i=r+1}^n sum_i$$来源是 $[r+1,n]$ 内部的数在 $3$ 操作后前缀和变成：$$(r-l+1)sum_r-S_l+S_r+sum_i-sum_r$$ $$=(r-l+1)sum_r-S_l+S_{r+1}+sum_i$$ 移项即得上述式子。 发现左右独立，直接让左式最小即可，和 2 的要求等价。

   所以，在经过深刻的分析后，我们得出结论：对于每个 $r$，最优的 $l=\operatorname{argmin}\limits_{i=1}^{pos} f_i(r)$。$f_i(x)$ 是一个一次函数，李超线段树维护即可。时间复杂度 $O(n\log n)$。

综上，我们在 $O(n\log n)$ 的时间复杂度内解决了这个问题。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,a[N],sum[N],ds[N],mns[N],fl,mx,mn,minn,flag,cnt[N];
struct line{
	int k,b;
	inline int num(int x){return k*x+b;}
};inline line lmin(line x,line y,int c){
	return x.num(c)<y.num(c)?x:y;
}struct Lichao{
	line sg[N<<3];
	inline void build(int x,int l,int r){
		sg[x]={0,(int)1e18};if(l==r) return;
		int mid=(l+r)>>1;build(x<<1,l,mid);
		build(x<<1|1,mid+1,r); 
	}inline void add(int x,int l,int r,line v){
		int mid=(l+r)>>1;
		if(sg[x].num(mid)>v.num(mid)) swap(sg[x],v);
		if(sg[x].num(l)>v.num(l)) add(x<<1,l,mid,v);
		if(sg[x].num(r)>v.num(r)) add(x<<1|1,mid+1,r,v);
	}inline line num(int x,int l,int r,int k){
		if(l==r) return sg[x];
		int mid=(l+r)>>1;line re=sg[x];
		if(k<=mid) return lmin(num(x<<1,l,mid,k),re,k);
		return lmin(num(x<<1|1,mid+1,r,k),re,k);
	}
}tr1,tr2;
inline int solve1(int x){
	for(int i=1,sm=0;i<=n;i++){
		sm+=(i<=x?sum[i]:a[i]);
		if(sm<0) return 0;
	}return x;
}inline pair<int,int>solve2(int x){
	tr1.build(1,-n,n);
	for(int l,r=1;r<x;r++){
		tr1.add(1,-n,n,{r,ds[r]});
		if(sum[r]>=0){
			l=tr1.num(1,-n,n,sum[r]).k;
			if((l-1)*sum[r]+ds[l]<=r*sum[r]+ds[r+1]+mns[r+1]) return {l,r};
		}
	}tr2.build(1,-n,n),tr1.add(1,-n,n,{1,ds[1]});
	for(int l,mid,r=x;r<=n;r++){
		tr2.add(1,-n,n,{r,ds[r]});
		if(sum[r]>=0){
			l=tr1.num(1,-n,n,sum[r]).k,mid=tr2.num(1,-n,n,sum[r]).k;
			if((l-1)*sum[r]+ds[l]<=r*sum[r]+ds[r+1]+mns[r+1])
				if((l-1)*sum[r]+ds[l]<=mid*sum[r]+ds[mid]) return {l,r};
		}
	}return {0,0};
}inline void solve(int id){
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];mns[n+1]=1e18;
	for(int i=n;i;i--) ds[i]=ds[i+1]+sum[i],mns[i]=min(mns[i+1],sum[i]);
	fl=0;while(sum[fl]>=0) fl++;fl=solve1(fl);
	if(fl) cout<<id<<(id%2?"\n1\n":"\n")<<"2 1 "<<fl<<"\n2 1 "<<n,exit(0);
	fl=0;while(sum[fl]>=0) fl++;pair<int,int>pr=solve2(fl);
	if(pr.first){
		cout<<id<<(id%2?"\n1\n":"\n")<<"3 "<<pr.first<<" ";
		cout<<pr.second<<"\n2 1 "<<n,exit(0);
	}for(int i=1;i<=n/2;i++) swap(a[i],a[n-i+1]);
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];mns[n+1]=1e18;
	for(int i=n;i;i--) ds[i]=ds[i+1]+sum[i],mns[i]=min(mns[i+1],sum[i]);
	fl=0;while(sum[fl]>=0) fl++;fl=solve1(fl);
	if(fl) cout<<id<<(id%2?"\n1\n":"\n")<<"3 "<<n-fl+1<<" "<<n<<"\n3 1 "<<n,exit(0);
	fl=0;while(sum[fl]>=0) fl++;pr=solve2(fl);
	if(pr.first){
		cout<<id<<(id%2?"\n1\n":"\n")<<"2 "<<n-pr.second+1<<" ";
		cout<<n-pr.first+1<<"\n3 1 "<<n,exit(0);
	}for(int i=1;i<=n/2;i++) swap(a[i],a[n-i+1]);
}signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>fl,fl=flag=1;
	for(int i=1;i<=n;i++){
		cin>>a[i],fl&=(a[i]<=0),flag&=(a[i]>=0);
		if(a[i]<0) mx=i,mn=(mn?mn:i);
	}if(flag) cout<<0,exit(0);
	if(fl) cout<<"1\n1",exit(0);
	for(int i=mn,sm=0;i<=mx;i++)
		sm+=a[i],minn=min(minn,sm);
	for(int i=mn-1;i;i--){
		minn+=a[i];if(minn>=0)
			cout<<"1\n2 1 "<<n,exit(0);
	}minn=0;
	for(int i=mx,sm=0;i>=mn;i--)
		sm+=a[i],minn=min(minn,sm);
	for(int i=mx+1;i<=n;i++){
		minn+=a[i];if(minn>=0)
			cout<<"1\n3 1 "<<n,exit(0);
	}solve(2),minn=mx=mn=0;
	for(int i=1;i<=n;a[i]=-a[i],i++)
		if(a[i]>0) mx=i,mn=(mn?mn:i);
	for(int i=mn,sm=0;i<=mx;i++)
		sm+=a[i],minn=min(minn,sm);
	for(int i=mn-1;i;i--){
		minn+=a[i];if(minn>=0)
			cout<<"2\n1\n2 1 "<<n,exit(0);
	}minn=0;
	for(int i=mx,sm=0;i>=mn;i--)
		sm+=a[i],minn=min(minn,sm);
	for(int i=mx+1;i<=n;i++){
		minn+=a[i];if(minn>=0)
			cout<<"2\n1\n3 1 "<<n,exit(0);
	}return solve(3),0;
}