n ≤\le≤ 3分类讨论即可
观察任意两名同学的起点,称起点在左边的为A,右边的为B,发现其可以交友的充要条件是他们的终点B在A的左侧。
将其扩展至很多同学,发现一些同学可以组成朋友圈的充要条件是,将同学按起点从左向右排序,他们的终点从右向左。
于是就设计数组 p[i]p[i]p[i],代表 A[i]A[i]A[i] 在 BBB 中的出现位置,原题转化为求 ppp 的最长不上升子序列。
使用您的 Hydro 通用账户