square1001君はとある競りを鑑賞していました。
競りとは、買い手が多数で品数に制限があるとき、高値を付けたものに買う権利を与える仕組みの取引です。(新明解国語辞典第七版より)
ここでの競りのルールは以下の通りです。
1. 次の 2. ～ 6. を品物が尽きるまで繰り返す
2. 新たな品物を出し、客に見せる
3. 客のうちの 1 人が好きな値段を品物につける
4. 客のうちの 1 人が現在品物についている値段よりも高い値段をつける
5. 4. の行為を行う客がいなくなるまで 4. を繰り返す
6. 品物に一番高い値段を付けた客がそれを落札する
square1001君はこの競り中に品物につけられた値段を時間順に全て記録しました。
その記録によると、$N$ 回品物に値段がつけられ、つけられた値段は最初から順に $A_1, A_2, A_3, \dots, A_N$ です。
E869120君はこの競りで何個の品物が出品されたか気になっています。
square1001君が作ったリストから、この競りで出品された品物の個数としてありうる最小値と最大値を求めてください。
入力は以下の形式で標準入力から与えられる。
$N$ $A_1$ $A_2$ $A_3$ $\cdots$ $A_N$
この競りで出品された品物の個数としてありうる最小値と最大値をこの順で改行区切りで出力してください。
ただし、最後には改行を入れること。
5 8 6 9 1 20
3 5
3 つの品物が順に、値段 8、値段 9、値段 20 で落札されたとき、品物の個数は最小値 3 となります。
6 3 3 4 3 3 4
4 6
8 5 5 4 4 3 3 2 2
8 8