시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 2286 315 216 22.360%

문제

이진 탐색 트리는 모든 노드가 많아야 2개의 자식 노드를 가지고 있는 트리이고, 각 노드에는 숫자가 하나씩 쓰여있다. 만약 어떤 노드에 써있는 숫자가 X라면, 그 노드의 왼쪽 서브트리에는 X보다 작은 수, 오른쪽 서브트리에는 X보다 큰 수만 저장되어 있어야 한다.

1보다 크거나 같고, N보다 작거나 같은 수 N개가 한 번씩 등장하는 수열이 입력으로 주어진다. 이 수열을 이용해서 이진 탐색 트리를 만드려고 한다. 즉, 수열의 첫번째 숫자부터, 마지막 숫자까지 이진 탐색 트리에 넣는 것이며, 각 숫자에 대해서 insert(X, root)를 차례대로 호출하는 것이다.

이진 탐색 트리에 삽입하는 함수는 다음과 같다.

insert(number X, node N)
    카운터 C값을 1 증가시킨다
    if X가 노드 N에 있는 숫자보다 작다면
        if N의 왼쪽 자식이 없다면
            X를 포함하는 새 노드를 만든 뒤, N의 왼쪽 자식으로 만든다
        else
            insert(X, N의 왼쪽 자식)
    else (X가 노드 N에 있는 숫자보다 크다면)
        if N의 오른쪽 자식이 없다면
            X를 포함하는 새 노드를 만든 뒤, N의 오른쪽 자식으로 만들기
        else
            insert(X, N의 오른쪽 자식)

        

각 숫자를 삽입한 후에 C의 값을 출력하는 프로그램을 작성하시오. 카운터 C의 값은 0으로 초기화되어 있다.

입력

첫째 줄에 수열의 크기 N이 주어진다. (1 ≤ N ≤ 300,000)

다음 N개의 줄에는 수열의 숫자가 차례대로 주어진다. 숫자는 구간 [1, N]에 포함되며, 모든 숫자는 중복되지 않는다.

출력

N개의 줄에 각 숫자가 트리에 삽입된 후에 카운터 C값을 한 줄에 하나씩 출력한다.

예제 입력 1

8
3
5
1
6
8
7
2
4

예제 출력 1

0
1
2
4
7
11
13
15

힌트

W3sicHJvYmxlbV9pZCI6IjI5NTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3NzRcdWM5YzQgXHVkMGQwXHVjMGM5IFx1ZDJiOFx1YjlhYyIsImRlc2NyaXB0aW9uIjoiPHA+XHJcblx0XHVjNzc0XHVjOWM0IFx1ZDBkMFx1YzBjOSBcdWQyYjhcdWI5YWNcdWIyOTQgXHViYWE4XHViNGUwIFx1YjE3OFx1YjRkY1x1YWMwMCBcdWI5Y2VcdWM1NDRcdWM1N2MgMlx1YWMxY1x1Yzc1OCBcdWM3OTBcdWMyZGQgXHViMTc4XHViNGRjXHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVkMmI4XHViOWFjXHVjNzc0XHVhY2UwLCBcdWFjMDEgXHViMTc4XHViNGRjXHVjNWQwXHViMjk0IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjNGYwXHVjNWVjXHVjNzg4XHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVjNWI0XHViNWE0IFx1YjE3OFx1YjRkY1x1YzVkMCBcdWMzNjhcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwXHVhYzAwIFhcdWI3N2NcdWJhNzQsIFx1YWRmOCBcdWIxNzhcdWI0ZGNcdWM3NTggXHVjNjdjXHVjYWJkIFx1YzExY1x1YmUwY1x1ZDJiOFx1YjlhY1x1YzVkMFx1YjI5NCBYXHViY2Y0XHViMmU0IFx1Yzc5MVx1Yzc0MCBcdWMyMTgsIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWMxMWNcdWJlMGNcdWQyYjhcdWI5YWNcdWM1ZDBcdWIyOTQgWFx1YmNmNFx1YjJlNCBcdWQwNzAgXHVjMjE4XHViOWNjIFx1YzgwMFx1YzdhNVx1YjQxOFx1YzViNCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQxXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIE5cdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWMyMTggTlx1YWMxY1x1YWMwMCBcdWQ1NWMgXHViYzg4XHVjNTI5IFx1YjRmMVx1YzdhNVx1ZDU1OFx1YjI5NCBcdWMyMThcdWM1ZjRcdWM3NzQgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHVjNzc0XHVjOWM0IFx1ZDBkMFx1YzBjOSBcdWQyYjhcdWI5YWNcdWI5N2MgXHViOWNjXHViNGRjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjOTg5LCBcdWMyMThcdWM1ZjRcdWM3NTggXHVjY2FiXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YmQ4MFx1ZDEzMCwgXHViOWM4XHVjOWMwXHViOWM5IFx1YzIyYlx1Yzc5MFx1YWU0Y1x1YzljMCBcdWM3NzRcdWM5YzQgXHVkMGQwXHVjMGM5IFx1ZDJiOFx1YjlhY1x1YzVkMCBcdWIxMjNcdWIyOTQgXHVhYzgzXHVjNzc0XHViYTcwLCBcdWFjMDEgXHVjMjJiXHVjNzkwXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBpbnNlcnQoWCwgcm9vdClcdWI5N2MgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1ZDYzOFx1Y2Q5Y1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1Yzc3NFx1YzljNCBcdWQwZDBcdWMwYzkgXHVkMmI4XHViOWFjXHVjNWQwIFx1YzBiZFx1Yzc4NVx1ZDU1OFx1YjI5NCBcdWQ1NjhcdWMyMThcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuaW5zZXJ0KG51bWJlciBYLCBub2RlIE4pXHJcbiAgICBcdWNlNzRcdWM2YjRcdWQxMzAgQ1x1YWMxMlx1Yzc0NCAxIFx1Yzk5ZFx1YWMwMFx1YzJkY1x1ZDBhOFx1YjJlNFxyXG4gICAgaWYgWFx1YWMwMCBcdWIxNzhcdWI0ZGMgTlx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YjJlNFx1YmE3NFxyXG4gICAgICAgIGlmIE5cdWM3NTggXHVjNjdjXHVjYWJkIFx1Yzc5MFx1YzJkZFx1Yzc3NCBcdWM1YzZcdWIyZTRcdWJhNzRcclxuICAgICAgICAgICAgWFx1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NThcdWIyOTQgXHVjMGM4IFx1YjE3OFx1YjRkY1x1Yjk3YyBcdWI5Y2NcdWI0ZTAgXHViNGE0LCBOXHVjNzU4IFx1YzY3Y1x1Y2FiZCBcdWM3OTBcdWMyZGRcdWM3M2NcdWI4NWMgXHViOWNjXHViNGUwXHViMmU0XHJcbiAgICAgICAgZWxzZVxyXG4gICAgICAgICAgICBpbnNlcnQoWCwgTlx1Yzc1OCBcdWM2N2NcdWNhYmQgXHVjNzkwXHVjMmRkKVxyXG4gICAgZWxzZSAoWFx1YWMwMCBcdWIxNzhcdWI0ZGMgTlx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YjJlNFx1YmE3NClcclxuICAgICAgICBpZiBOXHVjNzU4IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM3OTBcdWMyZGRcdWM3NzQgXHVjNWM2XHViMmU0XHViYTc0XHJcbiAgICAgICAgICAgIFhcdWI5N2MgXHVkM2VjXHVkNTY4XHVkNTU4XHViMjk0IFx1YzBjOCBcdWIxNzhcdWI0ZGNcdWI5N2MgXHViOWNjXHViNGUwIFx1YjRhNCwgTlx1Yzc1OCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjNzkwXHVjMmRkXHVjNzNjXHViODVjIFx1YjljY1x1YjRlNFx1YWUzMFxyXG4gICAgICAgIGVsc2VcclxuICAgICAgICAgICAgaW5zZXJ0KFgsIE5cdWM3NTggXHVjNjI0XHViOTc4XHVjYWJkIFx1Yzc5MFx1YzJkZCk8XC9wcmU+XHJcbjxwPiAmbmJzcDsgJm5ic3A7ICZuYnNwOyAmbmJzcDsmbmJzcDs8XC9wPlxyXG48cD5cclxuXHRcdWFjMDEgXHVjMjJiXHVjNzkwXHViOTdjIFx1YzBiZFx1Yzc4NVx1ZDU1YyBcdWQ2YzRcdWM1ZDAgQ1x1Yzc1OCBcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1Y2U3NFx1YzZiNFx1ZDEzMCBDXHVjNzU4IFx1YWMxMlx1Yzc0MCAwXHVjNzNjXHViODVjIFx1Y2QwOFx1YWUzMFx1ZDY1NFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbiIsImlucHV0IjoiXHJcbjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMjE4XHVjNWY0XHVjNzU4IFx1ZDA2Y1x1YWUzMCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMzAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHJcblx0XHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjMjJiXHVjNzkwXHViMjk0IFx1YWQ2Y1x1YWMwNCBbMSwgTl1cdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDE4XHViYTcwLCBcdWJhYThcdWI0ZTAgXHVjMjJiXHVjNzkwXHViMjk0IFx1YzkxMVx1YmNmNVx1YjQxOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0Tlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzAxIFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWQyYjhcdWI5YWNcdWM1ZDAgXHVjMGJkXHVjNzg1XHViNDFjIFx1ZDZjNFx1YzVkMCBcdWNlNzRcdWM2YjRcdWQxMzAgQ1x1YWMxMlx1Yzc0NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjk1NyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJTVCIsImRlc2NyaXB0aW9uIjoiPHA+QSBiaW5hcnkgc2VhcmNoIHRyZWUgaXMgYSB0cmVlIGluIHdoaWNoIGV2ZXJ5IG5vZGUgaGFzIGF0IG1vc3QgdHdvIGNoaWxkcmVuIG5vZGVzIChhIGxlZnQgYW5kIGEgcmlnaHQgY2hpbGQpLiBFYWNoIG5vZGUgaGFzIGFuIGludGVnZXIgd3JpdHRlbiBpbnNpZGUgaXQuIElmIHRoZSBudW1iZXIgWCBpcyB3cml0dGVuIGluc2lkZSBhIG5vZGUsIHRoZW4gdGhlIG51bWJlcnMgaW4gaXRzIGxlZnQgc3VidHJlZSBhcmUgbGVzcyB0aGFuIFggYW5kIHRoZSBudW1iZXJzIGluIGl0cyByaWdodCBzdWJ0cmVlIGFyZSBncmVhdGVyIHRoYW4gWC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+WW91IHdpbGwgYmUgZ2l2ZW4gYSBzZXF1ZW5jZSBvZiBpbnRlZ2VycyBiZXR3ZWVuIDEgYW5kIE4gKGluY2x1c2l2ZSkgc3VjaCB0aGF0IGVhY2ggbnVtYmVyIGFwcGVhcnMgaW4gdGhlIHNlcXVlbmNlIGV4YWN0bHkgb25jZS4gWW91IGFyZSB0byBjcmVhdGUgYSBiaW5hcnkgc2VhcmNoIHRyZWUgZnJvbSB0aGUgc2VxdWVuY2UsIHB1dHRpbmcgdGhlIGZpcnN0IG51bWJlciBpbiB0aGUgcm9vdCBub2RlIGFuZCBpbnNlcnRpbmcgZXZlcnkgb3RoZXIgbnVtYmVyIGluIG9yZGVyLiBJbiBvdGhlciB3b3JkcywgcnVuIGluc2VydChYLCByb290KSBmb3IgZXZlcnkgb3RoZXIgbnVtYmVyOiZuYnNwOzxcL3A+XHJcblxyXG48cHJlPlxyXG5pbnNlcnQoIG51bWJlciBYLCBub2RlIE4gKSBcclxuICAgIGluY3JlYXNlIHRoZSBjb3VudGVyIEMgYnkgMSBcclxuICAgIGlmIFggaXMgbGVzcyB0aGFuIHRoZSBudW1iZXIgaW4gbm9kZSBOIFxyXG4gICAgICAgIGlmIE4gaGFzIG5vIGxlZnQgY2hpbGQgXHJcbiAgICAgICAgICAgIGNyZWF0ZSBhIG5ldyBub2RlIHdpdGggdGhlIG51bWJlciBYIGFuZCBzZXQgaXQgdG8gYmUgdGhlIGxlZnQgY2hpbGQgb2Ygbm9kZSBOIFxyXG4gICAgICAgIGVsc2UgXHJcbiAgICAgICAgICAgIGluc2VydChYLCBsZWZ0IGNoaWxkIG9mIG5vZGUgTikgXHJcbiAgICBlbHNlIChYIGlzIGdyZWF0ZXIgdGhhbiB0aGUgbnVtYmVyIGluIG5vZGUgTikgXHJcbiAgICAgICAgaWYgTiBoYXMgbm8gcmlnaHQgY2hpbGQgXHJcbiAgICAgICAgICAgIGNyZWF0ZSBhIG5ldyBub2RlIHdpdGggdGhlIG51bWJlciBYIGFuZCBzZXQgaXQgdG8gYmUgdGhlIHJpZ2h0IGNoaWxkIG9mIG5vZGUgTiBcclxuICAgICAgICBlbHNlIFxyXG4gICAgICAgICAgICBpbnNlcnQoWCwgcmlnaHQgY2hpbGQgb2Ygbm9kZSBOKSBcclxuPFwvcHJlPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgY2FsY3VsYXRlcyB0aGUgdmFsdWUgb2YgdGhlIGNvdW50ZXIgQyBhZnRlciBldmVyeSBudW1iZXIgaXMgaW5zZXJ0ZWQuIFRoZSBjb3VudGVyIGlzIGluaXRpYWxseSAwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhlIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAzMDAwMDApLCB0aGUgbGVuZ3RoIG9mIHRoZSBzZXF1ZW5jZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHJlbWFpbmluZyBOIGxpbmVzIGNvbnRhaW4gdGhlIG51bWJlcnMgaW4gdGhlIHNlcXVlbmNlLCBpbnRlZ2VycyBpbiB0aGUgaW50ZXJ2YWwgWzEsIE5dLiBUaGUgbnVtYmVycyB3aWxsIGJlIGRpc3RpbmN0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBOIGludGVnZXJzIGVhY2ggb24gaXRzIG93biBsaW5lLCB0aGUgdmFsdWVzIG9mIHRoZSBjb3VudGVyIEMgYWZ0ZXIgZWFjaCBudW1iZXIgaXMgaW5zZXJ0ZWQgaW50byB0aGUgdHJlZS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=