====== 군인 ======

===== 풀이 =====
  * 문제 설명이 좀 이해하기 어렵게 되어있는데, 이해하고 나면 간단한 k번째수 쿼리 문제가 된다.
  * 군인들의 부대 번호를 집합에 저장한다고 생각하자. 1번 부대에 4명, 2번 부대에 3명, 3번 부대에 2명이면 {1,1,1,1,2,2,2,3,3} 이런식.
  * 이제 i번 군인이 몇번 부대냐고 묻는 것은, 저 집합에서 i번째로 큰 수가 뭐냐고 묻는 것과 동일하다. 
  * 부대의 감원과 증원은, 저 집합에서 i인 값을 a개 더하거나 빼는 것과 동일하다
  * 따라서 펜윅트리나 세그먼트 트리 기반의 [[ps:Order Statistic Tree]]를 사용하면 쉽게 이 두가지 쿼리를 처리할 수 있다. 두가지 연산 모두 O(logn)에 처리된다 
  * 전체 시간복잡도는 Order Statistic Tree를 구축하는데에 O(n), m개의 명령을 처리하는 데에 O(mlogn). 합쳐서 O(n+mlogn)이다

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 1321. 군인".

- Problem link: https://www.acmicpc.net/problem/1321
- Solution link: http://www.teferi.net/ps/problems/boj/1321
"""

import sys
from teflib import fenwicktree


def main():
    N = int(sys.stdin.readline())  # pylint: disable=unused-variable
    soldiers = fenwicktree.OrderStatisticTree(
        int(x) for x in sys.stdin.readline().split())
    M = int(sys.stdin.readline())
    for _ in range(M):
        query = [int(x) for x in sys.stdin.readline().split()]
        if query[0] == 1:
            soldiers.add(query[1] - 1, query[2])
        else:
            print(soldiers.kth(query[1]) + 1)


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:segmenttree#OrderStatisticTree|teflib.segmenttree.OrderStatisticTree]]

{{tag>BOJ ps:problems:boj:플래티넘_4}}