34405번 - 작은 수는 싫어!

문제

수를 가지고 노는 걸 좋아하는 정환은 생일날 아주 특별한 선물로 길이가 $N$인 배열 $A = [A_1, \cdots , A_N]$을 받았다.

그런데 이 배열 속에는 정환이 싫어하는 작은 수들이 섞여 있었다. 그래서 정환은 다음과 같은 두 가지 기술을 원하는 만큼 반복하여 작은 수들을 전부 없애버리기로 마음먹었다. 단, 배열이 비어 있다면 기술을 사용할 수 없다.

• 배열의 맨 앞이나 맨 뒤에 있는 수 하나를 버린다, 즉 $A_1$ 또는 $A_n$ 중 하나를 버린다.
• 배열 속 인접한 두 수를 합하여 하나로 합친다. 정확히는 1ドル \le i < n$인 $i$을 골라 두 수 $A_i,ドル $A_{i+1}$을 없애고, 그 자리에 $A_i+A_{i+1}$을 집어넣는다.
• 여기서 $n$은 해당 기술을 쓸 당시 배열에 남아 있는 수의 개수이며, 기술 수행 후에는 배열의 인덱스가 다시 매겨진다.

정환은 작은 수가 싫다고 했지만, 특별한 생일 선물인데 너무 많이 버리면 아깝다고 생각했다. 그래서 최대한 배열을 보존하기 위해 배열에 $K$보다 작은 수가 남아 있지 않도록 하면서도 남아 있는 수의 개수를 최대화하기로 했다.

정환이 최종적으로 남길 수 있는 수의 최대 개수를 구해보자.

입력

첫 번째 줄에 정수 $N,ドル $K$가 공백으로 구분되어 주어진다.

두 번째 줄에 $N$개의 정수 $A_1, \cdots ,A_N$이 공백으로 구분되어 주어진다.

출력

$K$보다 작은 수가 배열에 남아있지 않도록 조작한 후, 남길 수 있는 수의 최대 개수를 출력한다.

제한

• 1ドル \le N \le 1,000円,000円$
• $-10^9 \le K \le 10^9$
• $-10^9 \le A_i \le 10^9$ $(1 \le i \le N)$

힌트