시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (하단 참고) 128 MB 3219 441 293 23.199%

문제

이진 탐색 트리는 모든 노드가 많아야 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+XHVjNzc0XHVjOWM0IFx1ZDBkMFx1YzBjOSBcdWQyYjhcdWI5YWNcdWIyOTQgXHViYWE4XHViNGUwIFx1YjE3OFx1YjRkY1x1YWMwMCBcdWI5Y2VcdWM1NDRcdWM1N2MgMlx1YWMxY1x1Yzc1OCBcdWM3OTBcdWMyZGQgXHViMTc4XHViNGRjXHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVkMmI4XHViOWFjXHVjNzc0XHVhY2UwLCBcdWFjMDEgXHViMTc4XHViNGRjXHVjNWQwXHViMjk0IFx1YzIxOFx1YWMwMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjNGYwXHVjNWVjXHVjNzg4XHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVjNWI0XHViNWE0IFx1YjE3OFx1YjRkY1x1YzVkMCBcdWM0ZjBcdWM1ZWMgXHVjNzg4XHViMjk0IFx1YzIxOFx1YWMwMCBYXHViNzdjXHViYTc0LCBcdWFkZjggXHViMTc4XHViNGRjXHVjNzU4IFx1YzY3Y1x1Y2FiZCBcdWMxMWNcdWJlMGNcdWQyYjhcdWI5YWNcdWM1ZDBcdWIyOTQgWFx1YmNmNFx1YjJlNCBcdWM3OTFcdWM3NDAgXHVjMjE4LCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjMTFjXHViZTBjXHVkMmI4XHViOWFjXHVjNWQwXHViMjk0IFhcdWJjZjRcdWIyZTQgXHVkMDcwIFx1YzIxOFx1YjljYyBcdWM4MDBcdWM3YTVcdWI0MThcdWM1YjQgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+MVx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCBOXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjMjE4IE5cdWFjMWNcdWFjMDAgXHVkNTVjIFx1YmM4OFx1YzUyOSBcdWI0ZjFcdWM3YTVcdWQ1NThcdWIyOTQgXHVjMjE4XHVjNWY0XHVjNzc0IFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWMyMThcdWM1ZjRcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1Yzc3NFx1YzljNCBcdWQwZDBcdWMwYzkgXHVkMmI4XHViOWFjXHViOTdjIFx1YjljY1x1YjRkY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YzgxYyBcdWJjMzBcdWM1ZjRcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMyMThcdWI5N2MgXHViOGU4XHVkMmI4IFx1YjE3OFx1YjRkY1x1Yjg1YyBcdWIxOTNcdWFjZTAsIFx1YjJlNFx1Yjk3OCBcdWIwOThcdWJhMzhcdWM5YzAgXHVjMjE4XHViNGU0XHVjNzQ0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWMwYmRcdWM3ODVcdWQ1NThcdWJhNzRcdWMxMWMgXHVjNzc0XHVjOWM0IFx1ZDBkMFx1YzBjOSBcdWQyYjhcdWI5YWNcdWI5N2MgXHViOWNjXHViNGU0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjOTg5LCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzIxOFx1Yjk3YyBcdWM4MWNcdWM2NzhcdWQ1NWMgXHViYWE4XHViNGUwIFx1YzIxOFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgaW5zZXJ0KFgscm9vdClcdWI5N2MgXHVjMmU0XHVkNTg5XHVkNTU4XHViMjk0IFx1YWM4M1x1YWNmYyBcdWFjMTlcdWIyZTQuIFx1YWRmOCBcdWQ1NjhcdWMyMThcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVjOWM0IFx1ZDBkMFx1YzBjOSBcdWQyYjhcdWI5YWNcdWM1ZDAgXHVjMGJkXHVjNzg1XHVkNTU4XHViMjk0IFx1ZDU2OFx1YzIxOFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cHJlPlxyXG5pbnNlcnQobnVtYmVyIFgsIG5vZGUgTilcclxuICAgIFx1Y2U3NFx1YzZiNFx1ZDEzMCBDXHVhYzEyXHVjNzQ0IDEgXHVjOTlkXHVhYzAwXHVjMmRjXHVkMGE4XHViMmU0XHJcbiAgICBpZiBYXHVhYzAwIFx1YjE3OFx1YjRkYyBOXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMyMThcdWJjZjRcdWIyZTQgXHVjNzkxXHViMmU0XHViYTc0XHJcbiAgICAgICAgaWYgTlx1Yzc1OCBcdWM2N2NcdWNhYmQgXHVjNzkwXHVjMmRkXHVjNzc0IFx1YzVjNlx1YjJlNFx1YmE3NFxyXG4gICAgICAgICAgICBYXHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YjI5NCBcdWMwYzggXHViMTc4XHViNGRjXHViOTdjIFx1YjljY1x1YjRlMCBcdWI0YTQsIE5cdWM3NTggXHVjNjdjXHVjYWJkIFx1Yzc5MFx1YzJkZFx1YzczY1x1Yjg1YyBcdWI5Y2NcdWI0ZTBcdWIyZTRcclxuICAgICAgICBlbHNlXHJcbiAgICAgICAgICAgIGluc2VydChYLCBOXHVjNzU4IFx1YzY3Y1x1Y2FiZCBcdWM3OTBcdWMyZGQpXHJcbiAgICBlbHNlIChYXHVhYzAwIFx1YjE3OFx1YjRkYyBOXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMyMThcdWJjZjRcdWIyZTQgXHVkMDZjXHViMmU0XHViYTc0KVxyXG4gICAgICAgIGlmIE5cdWM3NTggXHVjNjI0XHViOTc4XHVjYWJkIFx1Yzc5MFx1YzJkZFx1Yzc3NCBcdWM1YzZcdWIyZTRcdWJhNzRcclxuICAgICAgICAgICAgWFx1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NThcdWIyOTQgXHVjMGM4IFx1YjE3OFx1YjRkY1x1Yjk3YyBcdWI5Y2NcdWI0ZTAgXHViNGE0LCBOXHVjNzU4IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM3OTBcdWMyZGRcdWM3M2NcdWI4NWMgXHViOWNjXHViNGU0XHVhZTMwXHJcbiAgICAgICAgZWxzZVxyXG4gICAgICAgICAgICBpbnNlcnQoWCwgTlx1Yzc1OCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjNzkwXHVjMmRkKTxcL3ByZT5cclxuXHJcbjxwPlx1YWMwMSBcdWMyMThcdWI5N2MgXHVjMGJkXHVjNzg1XHVkNTVjIFx1ZDZjNFx1YzVkMCBDXHVjNzU4IFx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjZTc0XHVjNmI0XHVkMTMwIENcdWM3NTggXHVhYzEyXHVjNzQwIDBcdWM3M2NcdWI4NWMgXHVjZDA4XHVhZTMwXHVkNjU0XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMjE4XHVjNWY0XHVjNzU4IFx1ZDA2Y1x1YWUzMCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMzAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWMyMThcdWFjMDAgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjMjE4XHViMjk0IFx1YWQ2Y1x1YWMwNCBbMSwgTl1cdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDFjIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YWNlMCwgXHVjOTExXHViY2Y1XHViNDE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5OXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjMDEgXHVjMjE4XHVhYzAwIFx1ZDJiOFx1YjlhY1x1YzVkMCBcdWMwYmRcdWM3ODVcdWI0MWMgXHVkNmM0XHVjNWQwIFx1Y2U3NFx1YzZiNFx1ZDEzMCBDXHVhYzEyXHVjNzQ0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyOTU3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQlNUIiwiZGVzY3JpcHRpb24iOiI8cD5BIGJpbmFyeSBzZWFyY2ggdHJlZSBpcyBhIHRyZWUgaW4gd2hpY2ggZXZlcnkgbm9kZSBoYXMgYXQgbW9zdCB0d28gY2hpbGRyZW4gbm9kZXMgKGEgbGVmdCBhbmQgYSByaWdodCBjaGlsZCkuIEVhY2ggbm9kZSBoYXMgYW4gaW50ZWdlciB3cml0dGVuIGluc2lkZSBpdC4gSWYgdGhlIG51bWJlciBYIGlzIHdyaXR0ZW4gaW5zaWRlIGEgbm9kZSwgdGhlbiB0aGUgbnVtYmVycyBpbiBpdHMgbGVmdCBzdWJ0cmVlIGFyZSBsZXNzIHRoYW4gWCBhbmQgdGhlIG51bWJlcnMgaW4gaXRzIHJpZ2h0IHN1YnRyZWUgYXJlIGdyZWF0ZXIgdGhhbiBYLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Zb3Ugd2lsbCBiZSBnaXZlbiBhIHNlcXVlbmNlIG9mIGludGVnZXJzIGJldHdlZW4gMSBhbmQgTiAoaW5jbHVzaXZlKSBzdWNoIHRoYXQgZWFjaCBudW1iZXIgYXBwZWFycyBpbiB0aGUgc2VxdWVuY2UgZXhhY3RseSBvbmNlLiBZb3UgYXJlIHRvIGNyZWF0ZSBhIGJpbmFyeSBzZWFyY2ggdHJlZSBmcm9tIHRoZSBzZXF1ZW5jZSwgcHV0dGluZyB0aGUgZmlyc3QgbnVtYmVyIGluIHRoZSByb290IG5vZGUgYW5kIGluc2VydGluZyBldmVyeSBvdGhlciBudW1iZXIgaW4gb3JkZXIuIEluIG90aGVyIHdvcmRzLCBydW4gaW5zZXJ0KFgsIHJvb3QpIGZvciBldmVyeSBvdGhlciBudW1iZXI6Jm5ic3A7PFwvcD5cclxuXHJcbjxwcmU+XHJcbmluc2VydCggbnVtYmVyIFgsIG5vZGUgTiApIFxyXG4gICAgaW5jcmVhc2UgdGhlIGNvdW50ZXIgQyBieSAxIFxyXG4gICAgaWYgWCBpcyBsZXNzIHRoYW4gdGhlIG51bWJlciBpbiBub2RlIE4gXHJcbiAgICAgICAgaWYgTiBoYXMgbm8gbGVmdCBjaGlsZCBcclxuICAgICAgICAgICAgY3JlYXRlIGEgbmV3IG5vZGUgd2l0aCB0aGUgbnVtYmVyIFggYW5kIHNldCBpdCB0byBiZSB0aGUgbGVmdCBjaGlsZCBvZiBub2RlIE4gXHJcbiAgICAgICAgZWxzZSBcclxuICAgICAgICAgICAgaW5zZXJ0KFgsIGxlZnQgY2hpbGQgb2Ygbm9kZSBOKSBcclxuICAgIGVsc2UgKFggaXMgZ3JlYXRlciB0aGFuIHRoZSBudW1iZXIgaW4gbm9kZSBOKSBcclxuICAgICAgICBpZiBOIGhhcyBubyByaWdodCBjaGlsZCBcclxuICAgICAgICAgICAgY3JlYXRlIGEgbmV3IG5vZGUgd2l0aCB0aGUgbnVtYmVyIFggYW5kIHNldCBpdCB0byBiZSB0aGUgcmlnaHQgY2hpbGQgb2Ygbm9kZSBOIFxyXG4gICAgICAgIGVsc2UgXHJcbiAgICAgICAgICAgIGluc2VydChYLCByaWdodCBjaGlsZCBvZiBub2RlIE4pIFxyXG48XC9wcmU+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCBjYWxjdWxhdGVzIHRoZSB2YWx1ZSBvZiB0aGUgY291bnRlciBDIGFmdGVyIGV2ZXJ5IG51bWJlciBpcyBpbnNlcnRlZC4gVGhlIGNvdW50ZXIgaXMgaW5pdGlhbGx5IDAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0aGUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDMwMDAwMCksIHRoZSBsZW5ndGggb2YgdGhlIHNlcXVlbmNlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgcmVtYWluaW5nIE4gbGluZXMgY29udGFpbiB0aGUgbnVtYmVycyBpbiB0aGUgc2VxdWVuY2UsIGludGVnZXJzIGluIHRoZSBpbnRlcnZhbCBbMSwgTl0uIFRoZSBudW1iZXJzIHdpbGwgYmUgZGlzdGluY3QuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IE4gaW50ZWdlcnMgZWFjaCBvbiBpdHMgb3duIGxpbmUsIHRoZSB2YWx1ZXMgb2YgdGhlIGNvdW50ZXIgQyBhZnRlciBlYWNoIG51bWJlciBpcyBpbnNlcnRlZCBpbnRvIHRoZSB0cmVlLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2008/2009 > Contest #3 5번

  • 문제를 번역한 사람: baekjoon
  • 잘못된 조건을 찾은 사람: Green55
  • 문제의 오타를 찾은 사람: jh05013
  • 어색한 표현을 찾은 사람: jyc4836

시간 제한 안내

아래 적혀있지 않은 시간 제한은 언어 도움말에 적혀있는 기준을 따른다.

  • Java: 5초
  • Java (OpenJDK): 5초
  • Java 11: 5초
  • Kotlin (JVM): 5초