사촌

시간 제한3초메모리 제한128 MB

요약
연속된 수 묶음으로 정의된 트리를 복원하고 노드 k의 사촌 노드 수를 셉니다.
난이도

보통10점 중 4점

유형
트리, 시뮬레이션
정답자
아직 제출이 없습니다

문제

증가하는 정수 수열로 트리를 만드는 규칙은 다음과 같다.

  • 수열의 첫 번째 정수가 트리의 루트 노드다.
  • 수열은 연속한 수끼리 묶여 여러 집합으로 나뉜다. 수가 연속하지 않는 자리에서 집합이 끊긴다.
  • 루트 바로 다음에 오는 집합이 루트의 자식이다. 이 집합의 첫 번째 수는 항상 루트 노드보다 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가 주어진다. (1≤n≤1,0001 \le n \le 1{,}000, 1≤k≤1,000,0001 \le k \le 1{,}000{,}000) 둘째 줄에 수열을 이루는 n개의 수가 주어진다. 모든 수는 1보다 크거나 같고 1,000,000보다 작거나 같으며, 수열은 항상 증가한다. k는 항상 수열에 들어 있는 수다.

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

출력

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

예제1

  1. 예제 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
    
    예상 출력
    5
    1
    0