LG ThinQ 是 LG 电子的 AI 平台，它能实时监控家用电器并为用户提供个性化服务。

一台配备 LG ThinQ 视觉 AI 的扫地机器人被放置在一个正方形的房间里。该机器人可以将房间划分为大小为 $10^9 \times 10^9$ 的网格，并确定每个网格单元是否被污染。我们将从上往数第 $y$ 行、从左往数第 $x$ 列的单元格称为单元格 $(x, y)$。机器人将 $N$ 个不同的受污染单元格的信息进行压缩，并按如下方式发送给服务器：

1. 将受污染单元格的 $(x, y)$ 坐标按照 $x$ 坐标升序排序（若 $x$ 坐标相同，则按 $y$ 坐标升序排序）。
2. 排序后移除 $x$ 坐标，仅将 $y$ 坐标按其顺序发送给服务器。

当两个受污染的单元格在水平或垂直方向上相邻时，我们认为这两个单元格属于同一个污染区域。服务器需要根据从机器人接收到的数据来估算污染区域的数量。给定发送给服务器的数据，求出可能的最少和最多污染区域数量。

输入格式

输入的第一行包含一个整数 $N$，表示受污染单元格的数量。($1 \le N \le 200\;000$)

接下来的 $N$ 行包含 $N$ 个整数 $y_1, \cdots, y_N$，表示服务器接收到的受污染单元格的 $y$ 坐标，每行一个数字。($1 \le y_i \le 10^9$)

输出格式

第一行输出可能的最少污染区域数量。

第二行输出可能最多污染区域数量。

样例

输入样例 1

6
1
3
4
1
2
3

输出样例 1

1
6