先考虑计算不强制有人留下的情况下最多留下多少人。设留下来的人的集合是 $S$，那么这个集合合法的条件可以写成 $\frac{p}{q|S|}\sum_{i\in S}a_i\ge \max_{i\in S}a_i$。考虑枚举 $\max_ia_i$，设它是 $lim$，那么当 $|S|$ 固定时，我们一定选择满足 $a_j\le lim$ 中 $a_j$ 最大的 $|S|$ 个元素。也就是说将 $a_i$ 从小到大排序后，若钦定 $a_r$ 是 $S$ 中最大值，那么最优方案一定是选择 $[1,r]$ 的一个后缀作为留下来的人。注意到若选择 $[l,r]$ 合法，由于 $a_l$ 是最小值所以 $a_l$ 一定小于等于平均值，把它扔掉一定使平均值上升，所以 $[l+1,r]$ 也合法，那么 $l_{\min}$ 就可以二分了。

假设上一步算得答案为 $k$，有 $[l_1,r_1],[l_2,r_2],\cdots,[l_m,r_m]$ 个区间长度是 $k$，在这些区间中的人显然一定能留下来。对于区间外一点 $p$，假设想从 $[l_i,r_i]$ 调整过来，一定是贪心地把 $l_i$ 扔掉换成 $p$ 这样新区间的平均值一定增大最多（或减小最少），那么按照 $r_i\le p$ 和 $l_i\ge p$ 把区间分成两类，对于每一类都可以简单推式子把 $p$ 和 $[l_i,r_i]$ 拆开变成一个前后缀最值的形式，判断 $p$ 是否能换到其中一侧的某个区间中即可。