宝宝题。

先考虑求出最多能选出多少人。

先对 $a$ 排序。枚举选择的薪水集合的最大值 $a_x$，那么平均数 $a_0 \ge a_x/K$。问题相当于在 $\{a_1,a_2,\dots,a_x\}$ 中选择一个子集 $S$ 使得子集和大于等于 $|S| a_x/K$。显然为了使和最大一定选一个后缀，直接二分可以得到当最大值钦定为 $a_x$ 时，后缀往前最远能选到的位置 $t_x$，那么最多能选择的人数为 $\mathrm{Ans}=\max_x \{x-t_x+1\}$。

考虑如何算出那些人一定不选。反向考虑多少人可能选，同样枚举最大值 $a_x$，要求 $x-t_x+1=\mathrm{Ans}$。对于 $\{a_1,\dots,a_x\}$，可能选的显然也是一个后缀。$a_{t_x}$ 到 $a_x$ 显然合法，平凡情况不再讨论。若 $y < t_x$ 也能选入，那么先钦定 $a_y$ 选进，后面为了和最大一定选 $[t_x+1,x]$。换言之，记平均数限制 $a_0=a_x/K$，只要满足 $a_y \ge \mathrm{Ans} \cdot a_0 - \sum_{i=t_x+1}^x a_i$，那么就可以选入。所以直接 lower_bound 即可得到最小的 $y$。那么 $[y,x]$ 都合法。需要支持区间标记 1，最后查询多少个位置还是 0，直接差分区间加法即可。复杂度 $O(n \log n)$。

由于 $a_x/K$ 是一个有理数不能直接算 $q/p$ 的商，会出现浮点数，所以预先对所有数乘以 $p$ 规避浮点问题。