터보소트

-홀수번째의 경우 고를 수 있는 수 중 가장 작은 수를 찾아서 앞으로 이동시켜야 하고 

-짝수번째의 경우 고를 수 있는 수 중 가장 큰 값을 찾아서 앞으로 이동해야한다. 

-이동 횟수를 내 앞 혹은 내 뒤에서 나까지의 인덱스 중 1의 개수를 세면 내가 이동해야 하는 횟수이다. 

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define MAXX 100001
using namespace std;
 
int n, tree[MAXX];
typedef pair<int, int> pp;
 
void update(int idx, int diff) {
    while(idx <= n) {
        tree[idx] += diff;
        idx += (idx&-idx);
    }
}
int sum(int idx) {
    int ret= 0;
    while(idx > 0) {
        ret += tree[idx];
        idx -= (idx&-idx);
    }
    return ret;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
 
    pp num[MAXX];
 
    for (int i = 1; i <= n; i++) {
        int tmp;
        cin >> tmp;
        num[i].first = tmp;
        num[i].second = i;
        update(i, 1); //1씩 자리를 늘려준다. 
        
    }
 
    sort(num+1, num+1+n);
 
    int left = 1, right = n;
    for (int i = 1; i <= n; i++) {
        
        if (i%2) {
            //큰 수 채우기 
            cout << sum(num[left].second) -1 << '\n';
            update(num[left].second, -1);
            left++;
        }
        else {
            cout << sum(n) - sum(num[right].second) << '\n';
            update(num[right].second, -1);
            right--;
        }
 
    }
    return 0;
}