Description

每一个机房中总有一个红太阳。有一天，AmberFrame 来到机房，发现桌上有不知道哪个蒟蒻放上的问 题： 有一个 n 个数的序列，一开始所有的数都是 0，每次可以将一个区间 [l, r](l ≤ r) 内的数 +1，求到达最 终状态的最少操作次数。 AmberFrame 非常强，自然不会把时间花在这种水题上。因此他就把任务交给了你，如果不会做的话，他 可能就会觉得你就是那个放问题的蒟蒻了而把你批判一番了。 

 

Input

第一行包含一个正整数 n，表示序列的长度。

第二行包含 n 个非负整数 a1, a2, ..., an，表示最终的状态。

Output

输出的第一行是一个正整数 m，表示最少的操作次数。 接下来 m 行每行两个正整数 li , ri，表示一次操作。你需要保证 1 ≤ li ≤ ri ≤ n。 保证最少次数 m ≤ 10^5，输出可以以任意顺序输出。 

 

Sample Input

62 3 3 3 3 3

Sample Output

31 61 62 6

 

Data Constraint

 

Hint

下发样例中第 i 个样例与第 i 组数据范围相符。

对于样例 1，第一个数被加了两次，其他每个数都被加了三次，显然满足条件。

分析

这题我TMD想复杂了

其实只用线段树记录区间最小值下标，然后分治一波就行，显然每次ans累加上最小值min减当前区间已减量delta

比赛时写了一波O3 inline register等卡时操作（并没有什么作用）

#pragma GCC optimize(3)#include 
      
       #include 
       
        #include 
        
         #include 
         
          #define l(x) t[x].l#define r(x) t[x].r#define m(x) t[x].mn#define s(x) t[x].posusing namespace std;const int N=1e5+1;struct Node {    int l,r,mn,pos;}t[4*N];struct Adep {    int l,r,dat;};int rt=1;int a[N];int ansl[N],ansr[N],cnt;int n;inline Adep In(int x,int y,int z) {    Adep a;a.l=x;a.r=y;a.dat=z;    return a;}inline void Build(int x,int l,int r) {    l(x)=l;r(x)=r;    if (l==r) {        m(x)=a[l];        s(x)=l;        return;    }    int mid=l+r>>1;    Build(x*2,l,mid);Build(x*2+1,mid+1,r);    m(x)=m(x*2);s(x)=s(x*2);    if (m(x)>m(x*2+1)) m(x)=m(x*2+1),s(x)=s(x*2+1);}inline int Query(int x,int l,int r) {    if (l>r(x)||r
          
           >1,ans=0,val=2147483647;    if (l<=mid) ans=Query(x*2,l,r),val=a[ans];    if (mid
           
            a[d]) val=a[d],ans=d; } return ans;}inline void Solve() { queue 
            
              q; while (!q.empty()) q.pop(); q.push(In(1,n,0)); while (!q.empty()) { Adep d=q.front();q.pop(); int l=d.l,r=d.r,dt=d.dat; int o=Query(rt,l,r),m=a[o],p=0; m-=dt; while (m) { ansl[++cnt]=l;ansr[cnt]=r; m--;p++; } if (l<=o-1) q.push(In(l,o-1,dt+p)); if (o+1<=r) q.push(In(o+1,r,dt+p)); }}int main() { freopen("range.in","r",stdin); freopen("range.out","w",stdout); scanf("%d",&n); for (register int i=1;i<=n;i++) scanf("%d",&a[i]); for (register int i=1;i<=4*n;i++) t[i].mn=2147483647; a[0]=2147483647; Build(rt,1,n); Solve(); printf("%d\n",cnt); for (register int i=1;i<=cnt;i++) printf("%d %d\n",ansl[i],ansr[i]); fclose(stdin);fclose(stdout);}