vector<double> runningMedian(vector<int> a)
{
  vector<int> tmpArr;
  for (int i : a)
    tmpArr.push_back(i);

  sort(tmpArr.begin(), tmpArr.end());
  reverse(a.begin(), a.end());

  vector<double> re;
  for (int i : a)
  {
    int mid = (tmpArr.size() - 1) / 2;
    double sum = tmpArr.at(mid);
    if (tmpArr.size() % 2 == 0)
    {
      sum += tmpArr.at(mid + 1);
      sum /= 2;
    }
    re.insert(re.begin(), sum);

    auto idx = find(tmpArr.begin(), tmpArr.end(), i);
    tmpArr.erase(idx);
  }

  return re;
}