# B. Difference Array

link : https://codeforces.com/contest/1707/problem/B

tóm tắt : cho a[], sort sẵn, tạo b[i] = a[i] - a[i - 1] và n = n - 1, hỏi sau n - 1 lần như vậy thì phần tử cuối là số mấy

ý tưởng : các số phân biệt xuất hiện trong các thao tác ko quá nhiều, cứ nén lại là được

code AC
:::spoiler

#include<bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define rev(i, a, b) for (int i = (a); i >= (b); --i)
#define ll long long

using namespace std;
const int mxn = 5e5 + 8;
int mark[mxn], a[mxn], b[mxn], cnt[mxn], cnt2[mxn];
int x = 1;

int ti(int t, int lan)
{
    if (lan == 0) return 0;
    if (mark[t] != x)
    {
        mark[t] = x;
        cnt2[t] = lan;
        return 1;
    } else cnt2[t] += lan;
    return 0;
}

int main(){
    //freopen("D:\\test.txt", "r", stdin);
    //freopen("D:\\test2.txt", "w", stdout);

    int t; cin >> t;
    while(t--)
    {
        ++x;
        int n, k = 0; cin >> n;
        rep(i, 1, n)
        {
            scanf("%d", &a[i]);
            b[k + 1] = a[i];
            k += ti(a[i], 1);
        }
        sort(b + 1, b + k + 1);
        n = k;
        rep(i, 1, n) a[i] = b[i];
        rep(i, 1, n) cnt[a[i]] = cnt2[a[i]];

        while(n > 1)
        {
            ++x;
            int k = 0;
            b[k + 1] = 0;
            k += ti(0, cnt[a[1]] - 1);

            rep(i, 2, n)
            {
                b[k + 1] = a[i] - a[i - 1];
                k += ti(a[i] - a[i - 1], 1);

                b[k + 1] = 0;
                k += ti(0, cnt[a[i]] - 1);
            }
            sort(b + 1, b + k + 1);
            n = k;
            rep(i, 1, n) a[i] = b[i];
            rep(i, 1, n) cnt[a[i]] = cnt2[a[i]];
            //rep(i, 1, n) cout << a[i] << '(' << cnt[a[i]] <<") "; cout << endl;
        }

        if (cnt[a[1]] > 1) printf("0\n");
        else printf("%d\n", a[1]);
    }
}

:::

bug : dùng chung mảng cnt với cnt2 là ko được