题目链接：https://www.acwing.com/problem/content/138/
参考链接：https://blog.csdn.net/sdz20172133/article/details/80101838
能进行算术运算的迭代器只有随即访问迭代器，要求容器元素存储在连续内存空间里，vector，string，deque的迭代器是有加减法的，但是map，set，multimap,multiset的迭代器是没有加减法的，list也不可以 。但是这些stl容器可以进行++和--的操作。
stl都是左闭右开的，就是说begin()是容器里面的第一个位置，end()是最后一个元素位置加一。
对于low_bound()和upper_bound()来说，前提：一个非降序列！！！！！！
题解：（平衡树解法）
把A1,A2,......An依次插入一个集合，则插入Ai之前，集合中保存的就是满足1<=j<i的所有Aj，而且是有序的。当Ai插入时，可能插入当前set的第一个位置，最后一个位置，或者中间某一个位置。其实就是对插入排序的优化。所以要求得最小差值，只需要比较Ai的前驱和后续位置的值。
#include<iostream>
#include<queue>
#include<set> using namespace std;
struct node{
int num;
int id;
bool operator <(node a) const{
return num<a.num;
}
};
set<node> s;
int main(){
int n;
cin>>n;
for (int i = 1; i <= n; ++i) {
int tmp;
cin>>tmp;
if (i==1) {
s.insert(node{tmp,i});
continue;
}
set<node>::iterator right= s.lower_bound(node{tmp,i});
set<node>::iterator left=right;
left--;
if (right==s.end()) {
cout<<tmp-left->num<<" "<<left->id<<endl;
}else if (right==s.begin()) {
cout<<right->num-tmp<<" "<<right->id<<endl;
}else if((tmp-left->num)<=(right->num-tmp)){
cout<<tmp-left->num<<" "<<left->id<<endl; }else{
cout<<right->num-tmp<<" "<<right->id<<endl; }
s.insert(node{tmp,i});
}
return 0;
}