#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <set>
#include <tuple>
#include <vector>

constexpr size_t length = 1048576;
constexpr size_t sample_length = 1000;

#define CALC_HEIGHT

#ifdef CALC_HEIGHT
constexpr int block_size = 2;
unsigned trailing_zeroes(size_t index) {
  unsigned bits = 0;
  unsigned x = index / block_size;

  if (x) {
    while (x % block_size == 0) {
      ++bits;
      x /= block_size;
    }
  }
  return bits;
}

unsigned int getHeight(long loc) {
  if (loc % block_size == 0) {
    auto level = trailing_zeroes(loc) + 1;
    return level - 1;
  }

  return 0;
}
#else
unsigned int getHeight(long loc) { return loc; }
#endif

std::vector<long long> population_vector, sample_vector;

void initialize(const std::vector<long long> &input_population,
                const std::vector<long long> &input_sample) {
  population_vector = input_population;
  std::sort(population_vector.begin(), population_vector.end());
  sample_vector = input_sample;
  std::sort(sample_vector.begin(), sample_vector.end());
}

long double sample_cdf(long double x) {
  auto it = lower_bound(sample_vector.begin(), sample_vector.end(), x);
  if (it == sample_vector.end()) {
    return 1;
  }
  if (it == sample_vector.begin()) {
    return 0;
  }
  auto it_prev = it - 1;
  return ((long double)(it_prev - sample_vector.begin()) +
          (long double)(x - *it_prev) / (*it - *it_prev)) /
         (long double)(sample_vector.size() - 1);
}

int infer_offset(double x) {
  return int(sample_cdf(x) * double(population_vector.size()));
}

// const double M_SQRT1_2 = sqrt(0.5);
constexpr long long s_avg = 2147483648;
constexpr long long s_stddev = 2147483648;

double goal_cdf(double x) { return erfc(-x * M_SQRT1_2) * 0.5; }
double stat_cdf(double x) { return goal_cdf((x - s_avg) / s_stddev); }

int main() {

  std::vector<long long> original_vector;

  std::set<long long> set1, set2;

  typedef std::tuple<int, int, long double> element_type;

  std::vector<element_type> location;

  FILE *file = fopen("normal_distribution.txt", "r");
  for (long long i; fscanf(file, "%lld ", &i) != EOF;
       original_vector.push_back(i), set1.insert(i))
    ;
  fclose(file);

  assert(original_vector.size() == set1.size());
  assert(original_vector.size() >= length);

  auto it = original_vector.begin();
  for (int i = 1; i <= sample_length; i++) {
    auto element = *it;
    auto ret = set2.insert(element);
    if (ret.second) {
      sample_vector.push_back(element);
      // printf("%lld\n", element);
    }
    it++;
  }

  assert(sample_vector.size() == sample_length);

  initialize(original_vector, sample_vector);

  for (auto iter = population_vector.begin(); iter != population_vector.end();
       iter++) {
    printf("%d,%d ", getHeight(infer_offset(*iter)),
           getHeight(iter - population_vector.begin()));
  }
  puts("");
  return 0;

  /*auto ita = set2.begin(), itb = set2.begin();
  itb++;
  long double dx = (*itb - *ita);
  int cnt1 = 0, cnt2 = 0;
  // for (auto it = set2.begin(); it != set2.end(); it++) printf("%lld ", *it);
  // printf("\n");
  long double e = 0;
  for (auto iter = set1.begin(); iter != set1.end(); iter++, cnt1++) {
    if (*iter <= *set2.begin()) {
      e += fabs(0.0 - double(cnt1) / (length - 1));
      printf("%.4lf ", 0.0);
      continue;
    }
    while (itb != set2.end() && *iter > *itb)
      ita++, itb++, dx = (*itb - *ita), cnt2++;
    if (*itb == *set2.end()) {
      e += fabs(1.0 - double(cnt1) / (length - 1));
      printf("%.4lf ", 100.0);
      continue;
    }
    // printf("%lld %lld %lld ", *ita, *it, *itb);
    long double res = (cnt2 + (*iter - *ita) / dx) / (sample_length - 1);
    auto single_e = std::abs(res - (long double)cnt1 / (length - 1));
    auto real_cnt2 = res * (length - 1) + 1;
    location.emplace_back(getHeight(cnt1),
                          getHeight((int)std::round(real_cnt2)), single_e);
    e += single_e;
    printf("%.4Lf ", res * 100);
  }
  printf("\n%.4Lf\n", e);
  for (auto element : location) {
    printf("%d,%d ", std::get<0>(element), std::get<1>(element));
  }
  puts("");
  return 0;*/
}