문제를 풀어갈 과정은 찾았는데... 자료구조에서 막히네요

1 2 3 4 5 6 7 8 9 10 11 12 에서

앞에 4개명의 작거나 같은 사람이 있다고 한다면, 4번째 숫자인 5를 제외한

1 2 3 4 6 7 8 9 10 11 12를 유지하고 5번째 작은 숫자인 145를 제외해줍니다.

마찬가지 방법으로

10번째인 11을 제외한 1 2 3 4 6 7 8 9 10 12 숫자는 172

7번째인 8을 제외한 1 2 3 4 6 7 9 10 12 숫자는 163

5번째인 6을 제외한 1 2 3 4 7 9 10 12 숫자는 155

8번째인 12를 제외한 1 2 3 4 7 9 10 숫자는 182

7번째인 10을 제외한 1 2 3 4 7 9 숫자는 167

....

입력으로 주어진 0 1 0 0 3 2 6 7 4 6 9 4 에서

뒤에서부터 읽으면 4 9 6 4 7 6 2 3 0 0 1 0 가 각각 자신의 앞에 있는 자신보다 키가 작거나 같은사람이고, 

그렇다면 앞에있는 사람만 보았을 때 자신의 키순번이 5 10 7 5 8 7 3 4 1 1 2 1 이기때문에 이 방법으로 구현하면 답은 나올 것 같아요.

이런식으로 초기 n개의 정렬된 자료구조에서 k번째 숫자를 빼는 것을 반복하는 것으로 구현하려고 하는데... 배열로 해도 시간복잡도는 n^2이고, list도 n^2,... 응용한다고 해서 union find로 해보려고 했는데 이것도 결국 n^2,.. 펜윅트리로 해보려고했는데도 이건 올바른 접근법이 아니더군요...

n개의 정렬된 구조에서 k번째 숫자를 logn time 이하로 빼내는 자료구조가 있을까요?

아니면 이 문제 해법 검색해도 안나오던데... 유사한 문제 해법이 있으면 알려주시면 감사하겠습니다...^^