// 첫 번째 풀이 : 시간 17%
var FreqStack = function () {
  this.count = {};
  this.bottom = new StackLayer();
};

var StackLayer = function () {
  this.stack = [];
  this.upper = null;
};

FreqStack.prototype.push = function (x) {
  this.count[x] = this.count[x] ? this.count[x] + 1 : 1;

  let current = this.bottom;
  let depth = this.count[x] - 1;

  while (depth > 0) {
    if (current.upper) {
      current = current.upper;
    } else {
      current.upper = new StackLayer();
      current = current.upper;
    }
    depth--;
  }

  current.stack.push(x);
};

FreqStack.prototype.pop = function () {
  let current = this.bottom;

  while (current.upper) {
    if (current.upper.stack.length) {
      current = current.upper;
    } else {
      break;
    }
  }

  const popped = current.stack.pop();
  this.count[popped]--;

  return popped;
};

// 두 번째 풀이 시간 98%

var FreqStack = function () {
  this.count = {};
  this.stacks = [null, []];
};

FreqStack.prototype.push = function (x) {
  this.count[x] = this.count[x] ? this.count[x] + 1 : 1;

  let floor = this.count[x];

  if (!this.stacks[floor]) {
    this.stacks[floor] = [];
  }

  this.stacks[floor].push(x);
};

FreqStack.prototype.pop = function () {
  const topStack = this.stacks.pop();

  const popped = topStack.pop();
  this.count[popped]--;

  if (topStack.length) {
    this.stacks.push(topStack);
  }

  return popped;
};