#P1268. 【挑战题】MP3

【挑战题】MP3

题目描述

有一种数字化一段录音的常用方式,是记录每一个时刻的强度值。这些非负的强度值就可以代表一段音频

对于一段音频,若有 KK 个不同的强度值,那么每一位我们都需要 k=log2Kk = \lceil\log_2K \rceil bit\text{bit} 来存储

也就是说,为了存储这一段音频,我们需要 nknkbit\text{bit}

为了压缩音频大小,我们们采取如下的方式:

选择两个整数 l,r(lr)l, r(l \leq r),对于音频的强度值序列 vv,将其作一次变换:

vi={vilvirlvi<lrr<viv_i = \begin{cases} v_i&l \leq v_i \leq r \\ l &v_i < l\\ r &r < v_i \end{cases}

其中第 2,32, 3 种情况被视作 viv_i 这个强度值被更改了

你的任务是对于给定的强度值序列 aa,找到一组 l,rl, r,使得在经过上述压缩后能够被大小为 I bytes(1byte = 8 bit)I \ \text{bytes} (\text{1byte = 8 bit}) 的存储器装下,并最小化被更改的强度值的数量

输入输出格式

输入格式

第一行包含两个正整数 n,I (n4105,I108)n,I \ (n \leq 4 \cdot 10^5, I \leq 10^8),描述了音量总时刻数与存储器大小

第二行包含 nn 个正整数

对于第 ii 个数,描述了 aia_i ( 0ai109 0 \le a_{i} \le 10^{9} ),即时刻 ii 的音量强度值

输出格式

输出答案,即在所有的适合存储器大小的压缩方案中,最小的被更改的强度值的数量

样例 #1

样例输入 #1

6 1
2 1 2 3 4 3

样例输出 #1

2

样例 #2

样例输入 #2

6 2
2 1 2 3 4 3

样例输出 #2

0

样例 #3

样例输入 #3

6 1
1 1 2 2 3 3

样例输出 #3

2

提示

在第一个例子中,我们可以选择 l=2,r=3 l=2, r=3 。数组变为 2 2 2 3 3 3,不同元素的数量为 K=2 K=2 ,只有两个值被改变。

在第二个例子中,不需要进行任何更改。

在第三个例子中,我们必须改变两个 1 或两个 3。