Не работает сортировка подсчётом в С++

Задача: отсортировать массив пар "ключ-значение" по ключу сортировкой подсчёта. Проблема: валится на некоторых тестах, таких, как 45894 5439345 32 979 194639 3478983 385025 3093494 32 35930

Или вот таких 5 34 98 23 1 55 234 78

Стандартный вектор использовать нельзя. Да и вообще контейнеры из STL. Код, который надо отладить:

#include <iostream>
#include <iomanip>
using namespace std;
typedef unsigned long long long_t;
class Index{
private:

long_t key, elem;
public:
    Index(int k, long_t e) : key(k), elem(e) {} //ключ(индекс), элемент(значение)
    Index() : key(), elem() {}
    friend Index* CountingSort(Index* obj, long_t max, size_t n); //объект(пара), максимальный элемент, количество элементов
    void Show(){
      cout << std::setw(6) << std::setfill('0') << key << "  " << elem << endl;
    }
    Index Set(long_t k, long_t e){//функция, помогающая нам связать пары
      elem = e;
      key  = k;
      return *this;
    }
  };
Index* CountingSort(Index* obj, long_t max, size_t n){//сортировка подсчётом
  long_t *c = new long_t[max];
  for (size_t i = 0; i < max ; ++i){
    c[i] = 0;
  }
  for (size_t i = 0; i < n; ++i){
    ++c[obj[i].key];
    c[obj[i].key] = obj[i].elem;
  }
  for (size_t j = 0, i = 0; j < max; ++j){
    if (c[j] != 0){
      obj[i].elem = c[j];
      obj[i].key  = j;
      c[j]--;
      ++i;
    }
  }
  delete[] c;
  return obj;
}
int main(){
  long_t e, k, max = 0;
  int n, i = 0;
  Index* a = new Index[10000];
while (cin >> k >> e){
  if(e > max) max = e;
  a[i].Set(k, e);
  i++;
}
n = i;
CountingSort(a, max, n);
for (int i = 0; i < n; i++){
  a[i].Show();
}
std::cin.clear();
std::cin.sync();
std::cin.get();
return 0;
}