没有详细证明，就不交题解了（而且这题题解也满了），只是提供另一种思路。

不妨把登山者分为 $s_i < a_i$ 和 $s_i \ge a_i$ 两类。

如果我们只单独考虑第一类，容易发现按照 $a_i$ 升序贪心考虑（能登山就登）一定是最优的；如果我们只单独考虑第二类，按照 $s_i$ 升序贪心考虑一定是最优的。这两个的证明是简单的。

那么显然考虑两种情况同时出现，首先可以证明的是同一类之间的登山者贪心的相对顺序是不变的，证明的话就考虑如果其与原顺序不同，我交换回来一定是不会劣的。

这样我们只需要考虑当前两类的最优决策 $u$ 和 $v$ 如何选择了：

• 如果 $a_u \le s_v$，那么我们选择 $u$ 不会对第二类决策产生任何影响，那不选白不选，我们当然会先选择 $u$。

• 否则你发现如果我们选了 $u$ 那就不能选 $v$ 了，且得到新的 $d'=a_u > s_v$。这不好，因为我们换成选择 $v$ 可以得到新的 $d''=\max\{d,a_v\}\le s_v < d'$，所以选择 $v$ 显然是更优的。

于是直接这样贪心即可。

仔细分析的话会发现这个思路与题解区按照 $(\max\{s_i,a_i\},s_i)$ 进行双关键字再贪心的思路本质相同，但是我个人认为这个思路更加自然明了（

code

不需要依赖双关键字