题目描述

导弹按顺序到达，一套系统可以拦截其中一个高度不升的子序列（后一次高度可以等于前一次）。求一套系统最多拦截多少枚，以及拦截全部导弹最少需要多少套系统。

输入格式

第一行导弹数量 $n$。第二行 $n$ 个高度。

输出格式

第一行输出最多拦截数；第二行输出最少系统数。

样例

8
389 207 155 300 299 170 158 65

6
2

数据范围

$1\le n\le1000$，高度为1至30000的整数。