二分答案 $x$，显然是把最小的 $(N+1)/2$ 个数变成 $\le x$。

要把 $A$ 变成 $x$，那么除掉的数至少应该是 $\lfloor A/(x+1)\rfloor +1$。

我们要 DP 求出选若干数的乘积至少是 $i$ 的最小代价。

首先先做一次后缀 $\max$，然后显然乘积不会超过 $2M$（超过 $M$ 时可以尽可能小，代价不会变大）。

然后我们 DP 求出乘积恰好为 $i$ 的最小代价，转移是枚举倍数，所以时间复杂度是 $O(M\log M)$。

最后再做一次后缀 $\max$。

时间复杂度 $O((N+M)\log M)$。