题目描述

某防御系统发射拦截弹攻击来袭目标。该系统有一个限制：第一发拦截弹可以到达任意高度，但之后每发拦截弹的射高都不能超过前一发。

给定各来袭目标依次出现时的高度，请回答两个问题：

1. 单套系统最多能拦截多少个目标？
2. 要拦截所有目标，最少需要多少套这样的系统？

输入格式

一行若干个正整数，用空格分隔，表示各目标依次出现的高度。

输出格式

第一行一个整数，表示单套系统最多能拦截的目标数。
第二行一个整数，表示最少需要的系统套数。

样例

389 207 155 300 299 170 158 65

6
2

提示

数据范围

• 前 $50\%$ 数据：目标个数不超过 $10^4$，高度为正整数且不超过 $5 \times 10^4$。
• 全部数据：目标个数不超过 $10^5$，高度为正整数且不超过 $5 \times 10^4$。

提示

第一问等价于求最长不上升子序列的长度；第二问等价于求最长上升子序列的长度（Dilworth 定理）。