通过两遍单调栈求出每个点作为最小值往右延伸到$g[i]$，作为最大值往左延伸到$f[i]$。
那么一个区间$[i,j]$可行当且仅当$g[i]geq j$、$f[j]leq i$且$i-a[i]==j-a[j]$。
按$i-a[i]$分组，从左往右考虑每个点作为$j$。
维护一个$g$单调递减的栈，那么最优的$i$只可能是栈顶。
如此求出所有固定右端点可能的最优左端点后，贪心求出所有极短合法区间即可。
时间复杂度$O(n)$。
#include<cstdio>
const int N=1100010,BUF=N*10;
char Buf[BUF],*buf=Buf;
inline void read(int&a){for(a=0;*buf<48;buf++);while(*buf>47)a=a*10+*buf++-48;}
int n,m,i,j,a[N],t,q[N],f[N],g[N],st[N*2],nxt[N],p[N],w[N],ans;
inline void add(int x,int y){nxt[y]=st[x];st[x]=y;}
inline void solve(){
if(m<2)return;
int i;
for(t=0,i=1;i<=m;i++){
int x=p[i];
while(t&&g[q[t]]<x)t--;
if(t&&q[t]>=f[x])w[x]=q[t];
while(t&&g[q[t]]<=g[x])t--;
q[++t]=x;
}
}
int main(){
fread(Buf,1,BUF,stdin);read(n);
for(i=1;i<=n;i++)read(a[i]);
for(i=1;i<=n;q[++t]=i++){
while(t&&a[q[t]]<a[i])t--;
f[i]=q[t]+1;
}
for(q[t=0]=n+1,i=n;i;q[++t]=i--){
while(t&&a[q[t]]>a[i])t--;
g[i]=q[t]-1;
}
for(i=n;i;i--)add(i-a[i]+n,i);
for(i=0;i<=n+n;i++){
for(m=0,j=st[i];j;j=nxt[j])p[++m]=j;
solve();
}
for(i=1,j=0;i<=n;i++)if(w[i])if(w[i]<=j)w[i]=0;else j=w[i],ans++;
printf("%d
",ans);
for(i=1;i<=n;i++)if(w[i])printf("%d %d
",w[i],i);
return 0;
}