对于一个序列 $a$，我们尝试分析 $a$ 的长度较短的子序列是否是糟糕的。

对于 $a$ 的一个长度为 $m$ 的子序列 $b$：

• 若 $m\leq 2$，易得 $b$ 不为糟糕的序列。

• 若 $m=3$，设 $b=\{b_0,\ b_1,\ b_2\}$，其中 $b_0\leq b_1\leq b_2$，则 $b$ 是糟糕的 $\Leftrightarrow b_0 < \dfrac{b_0+b_1+b_2}3 < b_1\leq b_2\Leftrightarrow b_0+b_2 < 2b_1$。

观察发现，对于一个好的序列 $a$，其长度为 $3$ 的子序列就必须有较多的性质。猜想：是否只需要考虑长度为 $3$ 的子序列？

设长度为 $m$ 的糟糕的序列 $b$ 的中位数为 $b_i$，其中 $i=\left\lceil\dfrac m2\right\rceil$。若 $b$ 的任意一个长度为 $3$ 的子序列都不是糟糕的序列，则由糟糕的序列的定义，且 $2b_i\leq b_j+b_{n-j+1}$，则

$$2\sum_{j=1}^mb_j=\sum_{j=1}^m\left(b_j+b_{n-j+1}\right)\geq 2mb_i \Rightarrow b_i\leq\frac 1m\sum_{j=1}^mb_j. $$

又由 $b$ 为一个糟糕的序列，易得 $b_i>\dfrac 1m\sum\limits_{j=1}^mb_j$，与上式矛盾。所以我们得出了——

引理 1： 对于任意一个糟糕的序列 $a$，都存在它的一个长度为 $3$ 的糟糕的子序列。

对于一个坏的序列 $a$，必定存在 $a$ 的一个子序列是糟糕的，又由引理 1 得必定存在这个糟糕子序列的一个糟糕的子序列长度为 $3$，而这个长度为 $3$ 的序列也是 $a$ 的子序列，于是我们就得出了——

引理 2： 对于一个序列 $a$，若不存在它的一个长度为 $3$ 的子序列是糟糕的，则 $a$ 必定是好的序列。

枚举要取出的子序列的最小值 $\alpha$，此时取数上界 $\beta=n$。则下一个选择的数 $x$ 必须满足 $2x\leq a_\alpha+a_\beta$，那么只需每次考虑贪心选择序列中属于区间 $(\alpha,\ \beta)$ 的数中满足 $2x\leq a_\alpha+a_\beta$ 的最大数 $x$，并将取数上界更新为 $x$ 即可。