SMMR-199: Pakiny & List

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5;
const int INF = 2e9;
int pos[N+10], neg[N+10];
int lp, ln;

int MX(int x){
    int l = 1, r = ln, mx = -INF;
    while(l <= r){
        int mid = (l + r)/2;
        if(neg[mid] < x){
            mx = max(mx, neg[mid]);
            l = mid + 1;
        }
        else r = mid - 1;
    }
    return mx;
}

int MN(int x){
    int l = 1, r = ln, mn = INF;
    while(l <= r){
        int mid = (l + r)/2;
        if(neg[mid] > x){
            mn = min(mn, neg[mid]);
            r = mid - 1;
        }
        else l = mid + 1;
    }
    return mn;
}

int main(){

    int n;
    scanf("%d", &n);

    for(int i=1;i<=n;i++) {
        int x;
        scanf("%d", &x);
        if(x >= 0) {
            lp ++;
            pos[lp] = x;
        }
        else {
            ln ++;
            neg[ln] = -x;
        }
    }

    sort(pos+1, pos+lp+1);
    sort(neg+1, neg+ln+1);

    int mn = INF;

    for(int i=1;i<lp;i++){
        mn = min(mn, abs(pos[i] - pos[i+1]));
    }

    for(int i=1;i<ln;i++){
        mn = min(mn, abs(neg[i] - neg[i+1]));
    }

    for(int i=1;i<=ln;i++){
        int mxx = MX(pos[i]);
        int mnn = MN(pos[i]);
        if(mxx != -INF) mn = min(mn, abs(pos[i] + mxx));
        if(mnn != INF) mn = min(mn, abs(pos[i] + mnn));
    }

    printf("%d", mn);

    return 0;
}