先求最少需要放逐的人数。不妨设 $a_1\ge a_2\ge \cdots\ge a_n$。显然留下的一定是一个区间。同时注意到对于一个合法的集合，删掉最小的数仍然合法。因此我们可以对每个左端点二分求出最大的右端点。

现在要求哪些人可能留下。显然我们只需要考虑把一个区间的最小值往右移让它更小，那么从左端点开始到最小值能移到的最远位置中间的人都是可能留下的。这个位置也可以二分或者直接解不等式。

时间复杂度 $O(n\log n)$。