首先分析一下上界。对于每个 $2\times 2$ 的小矩形，其中的最大值一定不是 sad 的。因此答案不可能超过 $2n-\left\lceil \frac{n}{2}\right\rceil$。

对于奇数 $n$ 来说，上界是可以达到的。只需要将最大的 $\left\lceil\frac{n}{2}\right\rceil$ 个数放在 $a_1,a_3,\ldots,a_n$ 的位置。这样对于 $b_{2k}$ 的位置就自动满足了，所以这些位置用来放接下来最大的一些数。然后容易发现将剩下的数有序放在剩下的空位即可满足条件。

对于偶数来说，上述构造方式只能做到 $\frac{3}{2}n-1$，这时因为最后的空位中放的最大的数是不满足 sad 的条件的。事实上这也就是偶数时真正的上界。如果想要达到 $\frac{3}{2}n$，那么一定是每个 $2\times 2$ 矩形中恰好有一个不 sad。也就是说，这些位置所在的列一定是所有的奇数列或偶数列，行则可以是任意的。确定这些位置后，考虑从大到小填数，首先可以把形如 $a_{2k}$ 和 $a_{2k+2}$ 已经填了的情况对应的 $b_{2k+1}$ 填上。之后发现就没有任何可以填的位置了，所以不可能有解。对照 $n$ 是奇数的情况，我们会发现因为 $a_1$ 和 $a_n$ 是相邻的，所以可以从 $b_1$ 或者 $b_n$ 开始填。