사촌
시간 제한3초메모리 제한128 MB
연속된 수 묶음으로 정의된 트리를 복원하고 노드 k의 사촌 노드 수를 셉니다.
문제
증가하는 정수 수열로 트리를 만드는 규칙은 다음과 같다.
- 수열의 첫 번째 정수가 트리의 루트 노드다.
- 수열은 연속한 수끼리 묶여 여러 집합으로 나뉜다. 수가 연속하지 않는 자리에서 집합이 끊긴다.
- 루트 바로 다음에 오는 집합이 루트의 자식이다. 이 집합의 첫 번째 수는 항상 루트 노드보다 2 이상 크므로, 루트는 혼자서 하나의 집합을 이룬다.
- 그 뒤의 집합은 차례대로 아직 자식이 없는 노드의 자식이 된다. 자식이 없는 노드가 둘 이상이면 그중 가장 작은 수를 가진 노드의 자식이 된다.
예를 들어 수열 1 3 4 5 8 9 15 30 31 32는 집합 {1}, {3, 4, 5}, {8, 9}, {15}, {30, 31, 32}로 나뉜다. 루트는 1이고 3, 4, 5가 1의 자식이다. 이어서 {8, 9}는 3의 자식, {15}는 4의 자식, {30, 31, 32}는 5의 자식이 된다.
부모가 서로 다르고 그 두 부모가 형제인 두 노드를 사촌이라고 한다.
수열과 노드 번호 k가 주어졌을 때 k의 사촌이 몇 개인지 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫째 줄에 노드의 수 n과 사촌의 수를 구할 노드의 번호 k가 주어진다. (, ) 둘째 줄에 수열을 이루는 n개의 수가 주어진다. 모든 수는 1보다 크거나 같고 1,000,000보다 작거나 같으며, 수열은 항상 증가한다. k는 항상 수열에 들어 있는 수다.
입력의 마지막 줄에는 0이 두 개 주어진다.
출력
각 테스트 케이스마다 k의 사촌의 수를 한 줄에 출력한다.