도시농부

송도고 급식실 앞 텃밭에서 도시농부 동아리 학생들이 상추를 기르고 있다.

상추는 오랜 시간과 정성을 들여 키운 끝에, 크기가 $m$ 이상이 되어야 비로소 수확할 수 있다.

즐겁게 텃밭을 가꾸고 계신 윤○○ 선생님의 모습이다.

하지만 오늘 점심 메뉴가 삼겹살이라서, 진서는 상추가 수확 가능한 상태까지 빨리 자라도록 영양제를 쓰기로 했다.

영양제는 A, B, C 세 종류가 있으며, 각 영양제의 효과는 다음과 같다.

• 영양제 A: 상추 세 개를 골라 사용한다. 셋 중 가장 큰 상추의 크기를 $x$라고 하면, 세 상추 모두의 크기가 $x$가 된다.
• 영양제 B: 상추 세 개를 골라 사용한다. 셋 중 가장 작은 상추의 크기를 $x$라고 하면, 세 상추 모두의 크기가 $x$만큼 증가한다.
• 영양제 C: 상추 한 개를 골라 사용한다. 그 상추의 크기가 $m$이 된다.

영양제는 동아리 예산으로 구입하므로, 함부로 쓰면 윤○○ 선생님께 혼날 것이다!

진서를 도와 모든 상추를 수확 가능하게 만드는 데 필요한 영양제의 총개수를 최소로 하는 프로그램을 작성하여라. 영양제로 인한 성장은 자연 성장보다 훨씬 빠르므로, 자연 성장은 고려하지 않는다.

첫 번째 줄에 상추의 개수 $n$과, 상추를 수확할 수 있는 최소 크기 $m$이 공백으로 구분되어 주어진다.

두 번째 줄에는 각 상추의 처음 크기 $s_1, s_2, \ldots, s_n$이 공백으로 구분된 $n$개의 정수로 주어진다.

모든 상추를 수확 가능하게 만드는 데 사용해야 하는 영양제 총개수의 최솟값을 출력한다.

• $3 \le n \le 100\,000$.
• $1 \le m \le 100\,000$.
• $1 \le s_i \le m$.

• 배추처럼 생겼지만 아무튼 상추이다.

• 본문의 영양제 설명을 수식으로 나타내면 다음과 같다.

  • 영양제 A: $(s_i, s_j, s_k)\leftarrow(\max\{s_i,s_j,s_k\}, \max\{s_i,s_j,s_k\}, \max\{s_i,s_j,s_k\})$
  • 영양제 B: $(s_i, s_j, s_k)\leftarrow(s_i+\min\{s_i,s_j,s_k\}, s_j+\min\{s_i,s_j,s_k\}, s_k+\min\{s_i,s_j,s_k\})$
  • 영양제 C: $(s_i)\leftarrow(m)$