周赛爆炸，但放假了！！！！
T1：水，赛事没打出来，鉴定为没独立思考能力导致的
T2：真水
T3：记录i之前的走法，正序倒叙交替就行了
T4：为了不重复，可以每一段和都由最短的一段转移过来，，可以证明这样算出的答案与和序列答案一一对应
考虑转移，发现如果一段和为0，则在往前都有sumj=sumi，不是最短，所以记录最后一个ans和相等的位置，则这一段和为0，之前的都不用转移了
#include<bits/stdc++.h>
using namespace std;
const int N=500005,mod=1000000007;
long long n,a,ans,cnt,dp[N];
map<long long,long long> mp;
int main(){
cin>>n;
cnt=1;
for(int i=1;i<=n;i++){
scanf("%lld",&a);
cnt=(cnt-mp[ans]+dp[i-1]+mod)%mod;
mp[ans]=dp[i-1];
ans+=a;
dp[i]=cnt;
}
cout<<dp[n];
}
T5：最后一根柱子能处理一个，倒二能处理2个，则倒三可以把点转移到倒一和倒二，还可以根据值域排序
依次类推，第i个柱子可以处理之前所有柱子能处理的数的数量和
（放个TJ）：可以把当前柱子上的圆盘一个一个拿出来，分配到右边的柱子上。如果把标号连续的圆盘分配在同一根柱子上，我们就把原问题分成了若干个子问题。（后面忘了）
#include<bits/stdc++.h>
using namespace std;
long long n,m,a[12005][15],f[20],top[20],tt[12005],kl,ss,ans[3000005],sum[3000005];
void move(int xx,int yy) {
ss++;
ans[ss]=xx;
sum[ss]=1;
top[yy]++;
a[top[yy]][yy]=a[top[xx]][xx];
top[xx]--;
}
void to(int xx,int yy) {
for(int i=xx; i<=yy-1; i++) {
move(i,i+1);
}
return ;
}
void ex_to(int xx,int yy)
{
top[yy]++;
a[top[yy]][yy]=a[1][xx];
top[yy]++;
a[top[yy]][yy]=a[2][xx];
top[xx]=0;
ss++;
ans[ss]=xx;
sum[ss]=2;
}
void work(int id,int l,int r) {
if(id==m) return ;
if(id==m-1) {
if(l==r) {
to(m-1,m);
} else {
if(a[1][id]>a[2][id]) {
to(m-1,m);
to(m-1,m);
} else {
ex_to(m-1,m);
}
}
return ;
}
// cout<<id<<endl<<l<<" "<<r<<endl;
if(l>r) return ;
kl=0;
for(int i=1; i<=m-id; i++) {
for(int j=1; j<=f[i]; j++) {
if(l+kl-1>r) break;
kl++;
tt[l+kl-1]=m-i+1;
}
}
for(int i=top[id]; i>=1; i--) {
// cout<<"#:"<<a[i][id]<<" "<<tt[a[i][id]]<<endl;
to(id,tt[a[i][id]]);
// cout<<top[id]<<endl;
}
for(int i=1; i<=m-id; i++) {
if(l+f[i]-1<r) {
work(m-i+1,l,l+f[i]-1);
l+=f[i];
} else {
work(m-i+1,l,r);
break;
}
}
return ;
}
int main() {
cin>>n>>m;
for(int i=1; i<=n; i++) {
scanf("%lld",&a[i][1]);
a[i][1]=n-a[i][1]+1;
// cout<<a[i][1]<<endl;
}
top[1]=n;
f[1]=1,f[2]=2;
for(int i=3; i<=15; i++) {
for(int j=1; j<=i-1; j++) {
f[i]+=f[j];
}
// cout<<f[i]<<endl;
}
work(1,1,n);
cout<<ss<<endl;
for(int i=1; i<=ss; i++) {
printf("%lld %lld\n",ans[i],sum[i]);
}
return 0;
}
//4 4
//3 2 4 1