[NOIP1999 普及组] 导弹拦截

题目描述

某国为应对敌方导弹的攻击，研发了一套导弹拦截装置。然而，这套系统存在一定的局限性：尽管其发射的第一枚炮弹可以达到任意高度，但后续发射的每一枚炮弹的高度均不得超过前一枚。某日，雷达监测到敌方导弹来袭。由于该系统尚处于试验阶段，仅配备了一套设备，因此可能无法成功拦截全部来袭导弹。

请根据导弹依次飞行的高度数据，计算该系统最多能够拦截多少枚导弹；同时，若要确保所有导弹均被拦截，最少需要配置多少套此类拦截系统。

输入格式

一行数据，包含多个整数，各数值之间通过空格进行分隔。

输出格式

输入包含两行数据，每行各有一个整数。其中第一行的数值代表该系统所能拦截的导弹最大数量，第二行的数值则表示为了拦截全部导弹所需配置的此类拦截系统最小套数。

输入输出样例分析

说明/提示

针对前 50%50% 的数据（即 NOIP 原题数据），所包含的导弹数量不会超过 20002000 个。该部分数据的总分值为 100100 分，采用 \mathcal O(n^2)O(n2) 的算法即可完成。
对于后 50%50% 的数据，其中导弹的数量上限为 10^5105 个。这部分数据的总分同样为 100100 分，需借助 \mathcal O(n\log n)O(nlogn) 的方法予以解决。

在所有测试