题目背景与 P2782 相同，区别在于：

1. 北岸的第 $i$ 个城市坐标固定为 $i$，只用输入南岸。
2. 共两个问，最大航线数与有多少种不同的修建方案能达到这个最大值。
3. $N$ 极大，$N \le 100000$。

第一个问已解决，第二个问咋整？