for(int i = 1; i <= n; ++i){
    scanf("%lld",&a[i].first);     
    a[i].second = i;
}

sort(a+1,a+n+1);

for(int i = 1; i <= n; ++i){
    b[a[i].second] = i;
}

В массиве B уже сжатый массив A.

Короче, есть три способа.

1. Посортить, как уже выше написали, пары (a[i], i). Потом в новый массив записывать числа по порядку на индексы a[i].second, при этом если a[i].first не меняется, записываемое число тоже не должно меняться.

2. Добавить все числа в сет. Потом пройтись по сету и сохранить в мапе, что первый элемент сета будет 1, второй элемент сета будет 2, и т.д. Потом заменить числа в исходном массиве как a[i] = mp[a[i]].

3. (мне кажется, это лучший способ) Посортить копию массива и убрать дубликаты. Потом бинпоиском найти позицию каждого элемента в этом массиве: a[i] = lower_bound(copy.begin(), copy.end(), a[i]) — copy.begin()

int a[maxn]; // исходный массив
int shr[maxn]; // сжатые координаты, shr -- от shrink
int k; // количество различных
for (int i = 0; i < n; ++i)
    shr[i] = a[i];
sort(shr, shr+n);
k = unique(shr, shr+n) - shr;

// индекс по исходному значению
int idx = lower_bound(shr, shr+k, val) - shr;

// исходное значение по индексу
int val = shr[idx];

Tips&tricks:

1. Добавить в массив shr 0 и MAXN (или правую/левую границу прямоугольника, если исходные числа -- это координаты точек в прямоугольнике). Так будет удобнее писать штуки на полуинтервалах.
2. Если нужен только относительный порядок, сразу после инициализации shr делаем

for (int i = 0; i < n; ++i)
    a[i] = lower_bound(shr, shr+k, a[i]) - shr;

и забываем про shr.

3. Не надо использовать map. Это в разы дольше, я так ловил TL-и. map стоит использовать только если координаты не известны заранее.

всегда пишу простой код с sort+lower_bound, но вообще можно обойтись одной сортировкой и одним дополнительным массивом:

void compress(vector<int>& a) {
  vector<int> b(a); // отсортированный массив индексов
  iota(b.begin(), b.end(), 0);
  sort(b.begin(), b.end(), [&a](int i, int j) { return a[i] < a[j]; });

  int add = 0, prev = 0;
  for (size_t i = 1; i < a.size(); ++i) {
    int add1 = a[b[i]] != a[b[i - 1]];
    prev = a[b[i - 1]] = prev + add;
    add = add1;
  }
  a[b.back()] = prev + add;
}

void compress(vector<int>& A) {
    map<int, int> M;
    for (int x : A)
        M[x]; // не опечатка
    int idx = 0;
    for (auto& it : M)
        it.second = idx++;
    for (int& x : A)
        x = M[x];
}