Description

表箱关有一个房间非常可怕，它由 n 个变异天启组成。 每个天启都会在进入房间后吐出绿弹并炸向某一个位置且范围内只有一个天启。若该位 置的天启已经死亡则没有事情发生，否则该位置的天启会死亡。每个天启只能且必须吐一次 绿弹（除非在它吐弹以前他就挂了）。 绿弹的飞行速度很快，在某个绿弹落地之前不会有新的绿弹被吐出。 虽然房间的天启位置和吐弹位置固定，但是吐弹顺序是随机的，所以 WSW 不能很好地制 定策略。 现在 WSW 想知道，最少和最多有几个天启被干掉。

Format

Input

第一行 n 表示天启个数。
第二行 n 个数 ai 表示 i 号天启的目标是 ai, ai=i
注意：行末有一个空格。

Output

一行两个数表示最少和最多有几个天启被干掉。

Sample 1

Input

8
2 3 2 2 6 7 8 5

Output

3 5

Limitation

1s, 131072KiB for each test case.

Hint

Source

高一年级信息学奥赛模拟考(二)