#P1078. 2023.3.11-第二题-天文爱好者

2023.3.11-第二题-天文爱好者

题目内容

塔子哥一直对天文学充满热情,他的房子位于一个相对较为偏远的地方,没有大城市那样的光污染,因此他拥有非常好的观测条件。他每晚都会抬头仰望星空,寻找流星的痕迹,记录下每颗流星出现和消失的时刻。

现在他收集了 nn 个流星在他所在观测地上空的出现时刻和消失时刻,对于一个流星,若其的出现时换为 ss ,消失时刻为 tt ,那么塔子哥在时间段 [s,t][s,t] 都能够观测到它。对于一个时刻, 观测地上空出现的流星数量越多,则塔子哥认为该时刻越好。

塔子哥希望能够选择一个最佳的时刻进行观测和摄影,使他能观测到最多数量的流星,现在塔子哥想知道,在这个最佳时刻,他最多能观测到多少个流星以及一共有多少个最佳时刻可供他选择。

输入描述

第一行是一个正整数 nn ,表示流星的数量。

第二行是 nn 个用空格隔开的正整数,第 ii个数 sis_i 表示第 ii 个流星的出现时间。

第三行是 nn 个用空格隔开的正整数,第 ii 个数 tit_i 表示第 ii 个流星的消失时间。

1n100000,1siti1051\le n\le 100000, 1\le s_i\le t_i\le 10^5

原题面是1e9,思考如何做~

输出描述

输出一行用空格隔开的两个数 xxyy ,其中 xx 塔子哥能观测到的最多流星数, yy 表示可供他选择的最佳时刻数量。

样例

输入

3
2 1 5
6 3 7

输出

2 4

样例解释

77 个时刻中,时刻 22225566 可以观测到 22 个流星,其他时刻只能观测到 11 个流星,所以最多能观测到的流星数量为 22 ,最佳时刻的数是 44