405354: GYM101911 K Medians and Partition

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

K. Medians and Partitiontime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Let median of some array be the number which would stand in the middle of this array if it was sorted beforehand. If the array has even length let median be smallest of of two middle elements. For example, median of the array $$$[10, 3, 2, 3, 2]$$$ is $$$3$$$ (i.e. $$$[2, 2, \underline{3}, 3, 10]$$$). Median of the array $$$[1, 5, 8, 1]$$$ is $$$1$$$ (i.e. $$$[1, \underline{1}, 5, 8]$$$).

Let array be $$$m$$$-good if its median is greater or equal than $$$m$$$.

Let the partition of array $$$[a_1, a_2, \dots, a_n]$$$ be a set of subarrays $$$\{b_1, b_2, \dots, b_k\}$$$ such that $$$b_1 = [a_1, a_2, \dots, a_{i_1}]$$$, $$$b_2 = [a_{i_1 + 1}, a_{i_1 + 2}, \dots, a_{i_2}]$$$, ..., $$$b_k = [a_{i_{k-1} + 1}, a_{i_{k-1} + 2}, \dots, a_n]$$$. For example, array $$$[10, 3, 2, 3, 2]$$$ can be partitioned as follows: $$$\{[10, 3, 2, 3, 2]\}$$$ or $$$\{[10], [3], [2], [3], [2]\}$$$, or $$$\{[10], [3, 2, 3, 2]\}$$$, or $$$\{[10, 3], [2], [3, 2]\}$$$ and so on.

You are given array $$$a$$$ of length $$$n$$$ and integer $$$m$$$. Find the partition of $$$a$$$ into maximum number of subarrays such that each subarray is $$$m$$$-good.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 5\,000$$$, $$$1 \le m \le 5\,000$$$) — length of array $$$a$$$ and constant $$$m$$$.

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 5\,000$$$)— array $$$a$$$.

Output

If there is no valid partition of array $$$a$$$ into $$$m$$$-good subarrays, print $$$0$$$. Otherwise print maximum number of subarrays in partition of array $$$a$$$ such that each subarray is $$$m$$$-good.

ExamplesInput
5 2
10 3 2 3 2
Output
5
Input
5 3
10 3 2 3 2
Output
1
Input
5 4
10 3 2 3 2
Output
0
Note

In the first example array can be partitioned into $$$5$$$ subarrays: $$$\{[10], [3], [2], [3], [2]\}$$$. Medians of each part greater of equal than $$$2$$$.

In the second example we can't partition array into several subarrays since medians of $$$[2]$$$, $$$[3, 2]$$$, $$$[2, 3, 2]$$$ and $$$[3, 2, 3, 2]$$$ are less than $$$3$$$.

加入题单

上一题 下一题 算法标签: