给一个 much simpler 的做法，main idea 是动态维护严格递增子序列和严格递减子序列。

• 依序考虑每一个元素，考察能够加入递增 / 递减子序列；
  • 仅能够加入到递增子序列：加入即可；
  • 仅能够加入到递减子序列：加入即可；
  • 不能够加入到任意一个子序列：无解；
  • 同时能加入到两个子序列中：若该元素后面紧邻的第一个元素大于该元素，则加入递增子序列，否则加入递减子序列，易证正确性。