LG ThinQ is LG Electronics' AI platform, which monitors home appliances in real time and provides users with personalized services.

A robotic vacuum with LG ThinQ vision AI is placed in a square-shaped room. This robot can split the room into a grid of size $10^9 \times 10^9$ and determine whether each cell is contaminated or not. Let's call the cell in the $y$-th row from the top and $x$-th column from the left as cell $(x, y)$. The robot compresses the information of $N$ distinct contaminated cells and sends it to the server as follows.

1. The $(x, y)$ coordinates of contaminated cells are sorted in the increasing order of $x$ coordinates (for equal $x$ coordinates, in increasing order of $y$ coordinates).
2. The $x$ coordinates are removed after sorting, and only the $y$ coordinates are sent to the server in their order.

When two contaminated cells are adjacent horizontally or vertically, we consider the two cells to be in the same contamination zone. The server should estimate the number of contamination zones from the data it received from the robot. Given the data that was sent to the server, find the minimum and maximum possible number of contamination zones.

Input

The first line of input contains an integer $N$, denoting the number of contaminated cells. ($1 \le N \le 200\;000$)

The following $N$ lines contain $N$ integers $y_1, \cdots, y_N$ representing the $y$ coordinates of the contaminated cells in the order received by the server, one number per line. ($1 \le y_i \le 10^9$)

Output

Print the minimum possible number of contamination zones in the first line.

Print the maximum possible number of contamination zones in the second line.

Examples

Input 1

6
1
3
4
1
2
3

Output 1

1
6