F. KK 与刷题
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
传言道：失败是成功之母。

想必大家在做题目的时候经常会出现 WA，TLE，MLE 等等问题，这些问题在 kk 身上依旧会发生。

这些年的竞赛时间中，kk 也是 WA 了无数次的男人。

但 kk 有一个习惯，每天都会记录下来他 WA 的次数，WA 的越多，他就认为他做的题目越来越难，自己的能力值也越来越高。

相反，如果他做题一路顺畅，那么他认为他的能力并没有被锻炼，自己的能力值反而会减少，具体计算能力值的方法如下：

  • 之前每有一天的 WA 的次数比今天多，都会使他的能力值 $$$-1$$$。
  • 之前每有一天的 WA 的次数比今天少，都会使他的能力值 $$$+1$$$。
  • 之前每有一天的 WA 的次数与今天相同，不会影响他的能力值。

每天的能力值将继承至下一天。初始能力为 $$$0$$$。

因为第一天没有 WA 的次数可以比较，所以第一天结束后，能力值不会改变。

求 kk 能力值最高时为多少，以及当前 kk 的能力值的大小

Input

第一行输入一个数 $$$n(1 \leq n \leq 10^5)$$$，代表 kk 已经训练的天数。

第二行输入 $$$n$$$ 个数字 $$$a_i(1 \leq a_i \leq 10^5)$$$, 表示 kk 每天的 WA 的次数。

Output

输出两个数，第一个数字代表 kk 能力值最高为多少，以及当前 kk 的最终能力值。

Examples
Input
3
1 3 2
Output
1 1
Input
3
2 1 3
Output
1 1
Input
4
1 5 4 1
Output
1 -1
Input
10
4 3 1 5 6 7 8 9 10 2
Output
30 23
Note

样例1：

  • 第一天 kk 能力值为 $$$0$$$。
  • 第二天 kk WA 了 $$$3$$$ 次，比第一天多，那么他的能力值加一，为 $$$1$$$。
  • 第三天 kk WA了 $$$2$$$ 次，比第一天多，那么他的能力值加一，比第二天少，那么他的能力值减一，最后还是为 $$$1$$$。
  • 三天中能力值最大的时候为 $$$1$$$。

样例2：

  • 第一天 kk 能力值为 $$$0$$$。
  • 第二天 kk WA了 $$$1$$$ 次，比第一天少，那么他的能力值减一，为 $$$-1$$$。
  • 第三天 kk WA了 $$$3$$$ 次，比第一天多，能力值加一，比第二天多，能力值有加一，那么最后他的能力值为 $$$1$$$。
  • 三天中能力值最大的时候为 $$$1$$$。

样例3：

  • 第一天 kk 能力值为 $$$0$$$。
  • 第二天 kk WA了 $$$5$$$ 次，比第一天多，那么他的能力值加一，为 $$$1$$$。
  • 第三天 kk WA了 $$$4$$$ 次，比第一天多，能力值加一，比第二天少，能力值减一，因此能力值仍为 $$$1$$$。
  • 第四天 kk WA了 $$$1$$$ 次，和第一天一样，能力值不变，比第二，三天都少，能力值减二，因此能力值为 $$$-1$$$。
  • 四天中能力值最大的时候为 $$$1$$$。

样例四：

  • 第一天 kk 能力值为0。
  • 第二天 kk WA了 3 次，比第一天少，那么他的能力值减 $$$1$$$，为 $$$-1$$$。
  • 第三天 kk WA了 1 次，比第一，二天少，那么他的能力值减 $$$2$$$，为 $$$-3$$$。
  • 第四天 kk WA了 5 次，比第一二三天多，那么他的能力值加 $$$3$$$，为 $$$0$$$。
  • 第五天 kk WA了 6 次，比第一二三四天多，那么他的能力值加 $$$4$$$，为 $$$4$$$。
  • 第六天 kk WA了 7 次，比第一二三四五天多，那么他的能力值加 $$$5$$$，为 $$$9$$$。
  • 第七天 kk WA了 8 次，比第一二三四五六天多，那么他的能力值加 $$$6$$$，为 $$$15$$$。
  • 第八天 kk WA了 9 次，比第一二三四五六七天多，那么他的能力值加 $$$7$$$，为 $$$22$$$。
  • 第九天 kk WA了 10 次，比第一二三四五六七八天多，那么他的能力值加 $$$8$$$，为 $$$30$$$。
  • 第十天 kk WA了 2 次，比第三天多，比第一二四五六七八九天少，那么他的能力值减 $$$7$$$，为 $$$23$$$。
  • 十天中能力最大为 $$$30$$$。