解题思路

我们需要在 $n$ 个标记互不相同的节点之间连尽可能多的无向边，且图中不能出现三个不同节点 $u,v,w$ 满足 $a_u \le a_v \le a_w$ 且 $u$ 与 $v$ 相连、$v$ 与 $w$ 相连。

关键观察：

• 若存在一条边连接标记为 $x$ 和 $y$ 的节点且 $x \le y$，则标记为 $y$ 的节点不能再与任何标记 $\le y$ 的其他节点相连，否则会立刻形成 $x \le y \le z$ 的连通三元组。
• 这等价于：我们可以将所有节点按标记值的大小分成两个集合 $L$ 和 $R$，要求 $L$ 中所有标记严格小于 $R$ 中所有标记，并且所有边都只能连接 $L$ 和 $R$ 中的节点（即完全二分图）。此时任意边的一个端点属于 $L$，另一个属于 $R$，不会出现中间节点同时连接两边的情况。
• 标记值相同的节点必须被完整地划分到同一侧（不能拆分），否则同一标记值的节点若分在两边，会存在 $a_u = a_v$ 且 $a_u \le a_v \le a_w$ 的可能，破坏限制。