#1151. 把你挂在地灵殿门口当装饰品!

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Komeiji Koishi

题目描述

恋恋最近想要在地灵殿门口再添加一些装饰品,于是去隙间要来了个罪袋,这些罪带按照质量依次编号为,恋恋筛选了一番,觉得其中编号小于等于的是合格的装饰品,其他的不是。

恋恋让罪袋们按照编号从小到大站成一队,带回地灵殿给姐姐看,不过姐姐认为恋恋选的个合格装饰品中,有一些仍然是不合格的,设在那个罪袋中姐姐认为依然不合格的罪袋有个(,且注意这个可以是编号小于等于的任意个,具体是哪些取决于姐姐的喜好)。那么现在有三类罪袋,即个恋恋和姐姐都认为合格类罪袋,个恋恋认为合格但姐姐认为不合格的类罪袋,个恋恋认为不合格的类罪袋。

于是,恋恋在无意识的情况下,给罪袋们重新排了队,但是重新排队的顺序安排有以下性质:

1.任何一个类罪袋前面没有类罪袋

2.对于队列中任何两个同一类型的罪袋(),一定是编号小的站在编号大的前面。

为什么要这么排队呢?因为,接下来恋恋就可以方便的直接杀掉排在最前面的类罪袋,并把他们挂在地灵殿门口当装饰品了!

你作为其中一个罪袋,不知道,不知道,你唯一知道的就是重新排队后的队列顺序(即一个数列,其中表示重排后队列第个人的编号)。

那么你到底会不会成为装饰品呢?为了计算概率,你需要算出的最小可能值和最大可能值。如果发现根本不可能有任何合法的,那么请输出

注意:(k-m)可能为零,鉴于题面较长,本题有任何题意上的疑惑欢迎进行询问

这个题到底是贪心还是二分呢?恋恋也不知道,嘻嘻嘻。

输入格式

第一行一个正整数,表示罪袋数量

接下来一行个正整数,表示数列

输出格式

一行两个非负整数用空格隔开,表示的最小可能值和最大可能值

当无解时输出,同样用空格隔开

样例

样例输入1

4
1 3 2 4

样例输出1

0 2

样例输入2

3
3 2 1

样例输出2

-1 -1

样例输入3

1
1

样例输出3

0 1

样例输入4

4
2 1 4 3

样例输出4

1 1

样例输入5

5
1 3 2 5 4

样例输出5

2 2

样例输入6

6
2 1 4 3 6 5

样例输出6

-1 -1

样例输入7

5
2 1 3 5 4

样例输出7

1 1

数据范围与提示