시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 364 89 76 25.166%

문제

증가하는 정수 수열을 이용해서 트리를 만드는 방법은 다음과 같다.

  • 첫 번째 정수는 트리의 루트 노드이다.
  • 다음에 등장하는 연속된 수의 집합은 루트의 자식을 나타낸다. 이 집합에 포함되는 수의 첫 번째 수는 항상 루트 노드+1보다 크다.
  • 그 다음부터는 모든 연속된 수의 집합은 아직 자식이 없는 노드의 자식이 된다. 그러한 노드가 여러 가지 인 경우에는 가장 작은 수를 가지는 노드의 자식이 된다.
  • 집합은 수가 연속하지 않는 곳에서 구분된다.

예를 들어, 수열 1 3 4 5 8 9 15 30 31 32를 위의 규칙을 이용해 트리를 만들면 아래 그림과 같이 된다.

두 노드의 부모는 다르지만, 두 부모가 형제(sibling)일 때 두 노드를 사촌이라고 한다.

수열 특정 노드 번호 k가 주어졌을 때, k의 사촌의 수를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 노드의 수 n과 사촌의 수를 구해야 하는 노드의 번호 k가 주어진다. (1 ≤ n ≤ 1,000, 1 ≤ k ≤ 1,000,000) 다음 줄에는 총 n개의 수가 주어지며, 모든 수는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 입력으로 주어지는 수열은 항상 증가한다. k는 항상 수열에 포함되는 수이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스 마다, k의 사촌의 수를 출력한다.

예제 입력 1

10 15
1 3 4 5 8 9 15 30 31 32
12 9
3 5 6 8 9 10 13 15 16 22 23 25
10 4
1 3 4 5 8 9 15 30 31 32
0 0

예제 출력 1

5
1
0
W3sicHJvYmxlbV9pZCI6Ijk0ODkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYWNcdWNkMGMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Yzk5ZFx1YWMwMFx1ZDU1OFx1YjI5NCBcdWM4MTVcdWMyMTggXHVjMjE4XHVjNWY0XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWQyYjhcdWI5YWNcdWI5N2MgXHViOWNjXHViNGRjXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjODE1XHVjMjE4XHViMjk0IFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWI4ZThcdWQyYjggXHViMTc4XHViNGRjXHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWIyZTRcdWM3NGNcdWM1ZDAgXHViNGYxXHVjN2E1XHVkNTU4XHViMjk0IFx1YzVmMFx1YzE4ZFx1YjQxYyBcdWMyMThcdWM3NTggXHVjOWQxXHVkNTY5XHVjNzQwIFx1YjhlOFx1ZDJiOFx1Yzc1OCBcdWM3OTBcdWMyZGRcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWM3NzQgXHVjOWQxXHVkNTY5XHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YjI5NCBcdWMyMThcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMyMThcdWIyOTQgXHVkNTZkXHVjMGMxIFx1YjhlOFx1ZDJiOCBcdWIxNzhcdWI0ZGMrMVx1YmNmNFx1YjJlNCBcdWQwNmNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YWRmOCBcdWIyZTRcdWM3NGNcdWJkODBcdWQxMzBcdWIyOTQgXHViYWE4XHViNGUwIFx1YzVmMFx1YzE4ZFx1YjQxYyBcdWMyMThcdWM3NTggXHVjOWQxXHVkNTY5XHVjNzQwIFx1YzU0NFx1YzljMSBcdWM3OTBcdWMyZGRcdWM3NzQgXHVjNWM2XHViMjk0IFx1YjE3OFx1YjRkY1x1Yzc1OCBcdWM3OTBcdWMyZGRcdWM3NzQgXHViNDFjXHViMmU0LiBcdWFkZjhcdWI3ZWNcdWQ1NWMgXHViMTc4XHViNGRjXHVhYzAwIFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzAgXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YzIxOFx1Yjk3YyBcdWFjMDBcdWM5YzBcdWIyOTQgXHViMTc4XHViNGRjXHVjNzU4IFx1Yzc5MFx1YzJkZFx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzlkMVx1ZDU2OVx1Yzc0MCBcdWMyMThcdWFjMDAgXHVjNWYwXHVjMThkXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWFjZjNcdWM1ZDBcdWMxMWMgXHVhZDZjXHViZDg0XHViNDFjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YzIxOFx1YzVmNCAxIDMgNCA1IDggOSAxNSAzMCAzMSAzMlx1Yjk3YyBcdWM3MDRcdWM3NTggXHVhZGRjXHVjZTU5XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NCBcdWQyYjhcdWI5YWNcdWI5N2MgXHViOWNjXHViNGU0XHViYTc0IFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jYy5wbmdcIiBzdHlsZT1cImhlaWdodDoyNDVweDsgd2lkdGg6MzIwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YjE3OFx1YjRkY1x1Yzc1OCBcdWJkODBcdWJhYThcdWIyOTQgXHViMmU0XHViOTc0XHVjOWMwXHViOWNjLCBcdWI0NTAgXHViZDgwXHViYWE4XHVhYzAwIFx1ZDYxNVx1YzgxYyhzaWJsaW5nKVx1Yzc3YyBcdWI1NGMgXHViNDUwIFx1YjE3OFx1YjRkY1x1Yjk3YyBcdWMwYWNcdWNkMGNcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyMThcdWM1ZjQgXHVkMmI5XHVjODE1IFx1YjE3OFx1YjRkYyBcdWJjODhcdWQ2Mzgga1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBrXHVjNzU4IFx1YzBhY1x1Y2QwY1x1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMTc4XHViNGRjXHVjNzU4IFx1YzIxOCBuXHVhY2ZjIFx1YzBhY1x1Y2QwY1x1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWIxNzhcdWI0ZGNcdWM3NTggXHViYzg4XHVkNjM4IGtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IG4gJmxlOyAxLDAwMCwgMSAmbGU7IGsgJmxlOyAxLDAwMCwwMDApIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjZDFkIG5cdWFjMWNcdWM3NTggXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHViYWE4XHViNGUwIFx1YzIxOFx1YjI5NCAxXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIDEsMDAwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YzIxOFx1YzVmNFx1Yzc0MCBcdWQ1NmRcdWMwYzEgXHVjOTlkXHVhYzAwXHVkNTVjXHViMmU0LiBrXHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWMyMThcdWM1ZjRcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDE4XHViMjk0IFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWI0NTAgXHVhYzFjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWI5YzhcdWIyZTQsIGtcdWM3NTggXHVjMGFjXHVjZDBjXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTQ4OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNvdW50IHlvdXIgQ291c2lucyIsImRlc2NyaXB0aW9uIjoiPHA+QSB0cmVlIGlzIGZvcm1lZCBmcm9tIGEgc3RyaWN0bHkgaW5jcmVhc2luZyBzZXF1ZW5jZSBvZiBpbnRlZ2VycyBhcyBmb2xsb3dzOiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlRoZSBmaXJzdCBpbnRlZ2VyIGluIHRoZSBzZXF1ZW5jZSBpcyB0aGUgcm9vdCBvZiB0aGUgdHJlZSZuYnNwOzxcL2xpPlxyXG5cdDxsaT5UaGUgbmV4dCBzZXQgb2YgY29uc2VjdXRpdmUgaW50ZWdlcnMgaW4gdGhlIHNlcXVlbmNlIGRlc2NyaWJlcyB0aGUgY2hpbGRyZW4gb2YgdGhlIHJvb3QuIFRoZSBmaXJzdCBvZiB0aGVzZSB3aWxsIGJlIGdyZWF0ZXIgdGhhbiByb290KzEuJm5ic3A7PFwvbGk+XHJcblx0PGxpPkZyb20gdGhlcmUsIGVhY2ggc2V0IG9mIGNvbnNlY3V0aXZlIGludGVnZXJzIGRlc2NyaWJlcyB0aGUgY2hpbGRyZW4gb2YgdGhlIGxvd2VzdCBudW1iZXJlZCBub2RlIHdoaWNoIGRvZXMgbm90IHlldCBoYXZlIGNoaWxkcmVuLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5Ob24tY29uc2VjdXRpdmUgaW50ZWdlcnMgbWFyayBhIGJyZWFrIGJldHdlZW4gb25lIHNldCBvZiBjaGlsZHJlbiBhbmQgdGhlIG5leHQuJm5ic3A7PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIHRoZSBzZXF1ZW5jZTombmJzcDs8XC9wPlxyXG5cclxuPHA+MSAzIDQgNSA4IDkgMTUgMzAgMzEgMzImbmJzcDs8XC9wPlxyXG5cclxuPHA+V291bGQgcHJvZHVjZSB0aGUgZm9sbG93aW5nIHRyZWU6Jm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvY2MucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjQ1cHg7IHdpZHRoOjMyMHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlR3byBub2RlcyBhcmUgY29uc2lkZXJlZCB0byBiZSBDb3VzaW5zIGlmIHRoZXkgaGF2ZSBkaWZmZXJlbnQgcGFyZW50cywgYnV0IHRoZWlyIHBhcmVudHMgYXJlIHNpYmxpbmdzLiBHaXZlbiBhIHRyZWUgYW5kIGEgcGFydGljdWxhciBub2RlIG9mIHRoYXQgdHJlZSwgY291bnQgdGhlIG51bWJlciBvZiBDb3VzaW5zIG9mIHRoZSBub2RlLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlcmUgd2lsbCBiZSBzZXZlcmFsIHRlc3QgY2FzZXMgaW4gdGhlIGlucHV0LiBFYWNoIHRlc3QgY2FzZSB3aWxsIGJlZ2luIHdpdGggYSBsaW5lIHdpdGggdHdvIGludGVnZXJzLCBuICgxJmxlO24mbGU7MSwwMDApIGFuZCBrICgxJmxlO2smbGU7MSwwMDAsMDAwKSwgd2hlcmUgbiBpcyB0aGUgbnVtYmVyIG9mIG5vZGVzIGluIHRoZSB0cmVlLCBhbmQgayBpcyB0aGUgcGFydGljdWxhciBub2RlIG9mIGludGVyZXN0LiBPbiB0aGUgZm9sbG93aW5nIGxpbmUgd2lsbCBiZSBuIGludGVnZXJzLCBhbGwgaW4gdGhlIHJhbmdlIGZyb20gMSB0byAxLDAwMCwwMDAsIGFuZCBndWFyYW50ZWVkIHRvIGJlIHN0cmljdGx5IGluY3JlYXNpbmcuIFRoZXNlIGRlc2NyaWJlIHRoZSB0cmVlLCBpbiB0aGUgbWFubmVyIGRlc2NyaWJlZCBhYm92ZS4gVGhlIGludGVnZXJzIHdpbGwgYmUgc2VwYXJhdGVkIHdpdGggYSBzaW5nbGUgc3BhY2UuIFRoZXJlIHdpbGwgYmUgbm8gZXh0cmEgc3BhY2VzLiBUaGUgdmFsdWUgayBpcyBndWFyYW50ZWVkIHRvIGJlIG9uZSBvZiB0aGUgaW50ZWdlcnMgb24gdGhlIHNlY29uZCBsaW5lLiBJbnB1dCB3aWxsIGVuZCB3aXRoIGEgbGluZSB3aXRoIHR3byAwcy4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCBhIHNpbmdsZSBpbnRlZ2VyLCBpbmRpY2F0aW5nIHRoZSBudW1iZXIgb2YgY291c2lucyBvZiBub2RlIGsuIE91dHB1dCBubyBzcGFjZXMsIGFuZCBkbyBub3Qgc2VwYXJhdGUgYW5zd2VycyB3aXRoIGJsYW5rIGxpbmVzLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==