（一）
出门左转 P3369。
只需要同时记录原本属于哪一位即可。
这里给出 Splay 做法。
（二）
AC 代码。
建议自己打一遍巩固印象。虽然我是直接拉过来的。
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
int n,rt,cnt;
struct node{
int msiz,tsiz,val,ch[2],f,id;
}tree[1000010];
void maintain(int o){
if(!o)return;
tree[o].tsiz=tree[o].msiz;
if(tree[o].ch[0])tree[o].tsiz+=tree[tree[o].ch[0]].tsiz;
if(tree[o].ch[1])tree[o].tsiz+=tree[tree[o].ch[1]].tsiz;
}
int get(int o){
return tree[tree[o].f].ch[1]==o;
}
void clear(int o){
tree[o].ch[0]=tree[o].ch[1]=tree[o].f=tree[o].msiz=tree[o].tsiz=0;
}
int find_pre(){
int o=tree[rt].ch[0];
while(tree[o].ch[1])o=tree[o].ch[1];
return o;
}
int find_nxt(){
int o=tree[rt].ch[1];
while(tree[o].ch[0])o=tree[o].ch[0];
return o;
}
void rotate(int o){
int fa=tree[o].f,ffa=tree[fa].f,pos=get(o);
tree[fa].ch[pos]=tree[o].ch[pos^1];
tree[tree[fa].ch[pos]].f=fa;
tree[o].ch[pos^1]=fa;
tree[fa].f=o;
tree[o].f=ffa;
if(ffa)tree[ffa].ch[tree[ffa].ch[1]==fa]=o;
maintain(fa);
maintain(o);
}
void splay(int o){
for(int fa;fa=tree[o].f;rotate(o))
if(tree[fa].f)rotate((get(o)==get(fa))?fa:o);
rt=o;
}
void insert(int x,int id){
if(!rt){
cnt++;
rt=cnt;
tree[cnt].ch[0]=tree[cnt].ch[1]=0;
tree[cnt].f=0;
tree[cnt].msiz=tree[cnt].tsiz=1;
tree[cnt].val=x;
tree[cnt].id=id;
return;
}
int o=rt,fa=0;
while(1){
if(x==tree[o].val){
tree[o].msiz++;
maintain(o);
maintain(fa);
splay(o);
break;
}
fa=o;
o=tree[o].ch[x>tree[o].val];
if(!o){
cnt++;
tree[cnt].ch[0]=tree[cnt].ch[1]=0;
tree[cnt].msiz=tree[cnt].tsiz=1;
tree[cnt].val=x;
tree[cnt].f=fa;
tree[cnt].id=id;
tree[fa].ch[tree[fa].val<x]=cnt;
maintain(fa);
splay(cnt);
break;
}
}
}
int find_rank(int x){
int ans=0,o=rt;
while(1){
if(x<tree[o].val)o=tree[o].ch[0];
else{
if(tree[o].ch[0])ans+=tree[tree[o].ch[0]].tsiz;
if(x==tree[o].val){
splay(o);
return ans+1;
}
ans+=tree[o].msiz;
o=tree[o].ch[1];
}
}
}
void remove(int x){
int r=find_rank(x);
if(tree[rt].msiz>1){
tree[rt].msiz--;
maintain(rt);
return;
}
if(!tree[rt].ch[0]&&!tree[rt].ch[1]){
clear(rt);
rt=0;
}
else if(!tree[rt].ch[0]){
int xx=rt;
rt=tree[rt].ch[1];
tree[rt].f=0;
clear(xx);
}
else if(!tree[rt].ch[1]){
int xx=rt;
rt=tree[rt].ch[0];
tree[rt].f=0;
clear(xx);
}
else{
int pos=find_pre(),xx=rt;
splay(pos);
tree[rt].ch[1]=tree[xx].ch[1];
tree[tree[xx].ch[1]].f=rt;
clear(xx);
maintain(rt);
}
}
node find_val(int x){
int o=rt;
while(1){
if(tree[o].ch[0]&&tree[tree[o].ch[0]].tsiz>=x)o=tree[o].ch[0];
else{
int s=(tree[o].ch[0]?tree[tree[o].ch[0]].tsiz:0)+tree[o].msiz;
if(x<=s)return tree[o];
x-=s;
o=tree[o].ch[1];
}
}
}
signed main(){
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
n=read();
for(int i=1;i<=n;i++){
int x=read();
insert(x,i);
if(i==1)continue;
int rk=find_rank(x);
if(rk==1){
node t=find_val(2);
printf("%lld %lld\n",t.val-x,t.id);
}
else if(rk==i){
node t=find_val(i-1);
printf("%lld %lld\n",x-t.val,t.id);
}
else{
node t1=find_val(rk-1),t2=find_val(rk+1);
if(x-t1.val<=t2.val-x)printf("%lld %lld\n",x-t1.val,t1.id);
else printf("%lld %lld\n",t2.val-x,t2.id);
}
}
return 0;
}