Farmer John có \(N\) con bò luôn lạc ra các vùng xa của trang trại! Ông cần sự giúp đỡ của bạn để tập hợp chúng lại với nhau.

Cánh đồng chính của trang trại dài và hẹp – chúng ta có thể coi nó như một trục số, trên đó một con bò có thể ở bất kỳ vị trí số nguyên nào. Các con bò hiện tại đang ở các vị trí số nguyên khác nhau, và Farmer John muốn di chuyển chúng sao cho chúng chiếm các vị trí liên tiếp (ví dụ: các vị trí 3, 4, 5, 6, 7, và 8).

Đáng tiếc là các con bò khá buồn ngủ, và Farmer John gặp khó khăn trong việc thu hút sự chú ý của chúng để di chuyển. Vào bất kỳ thời điểm nào, ông chỉ có thể di chuyển một con bò nếu nó là điểm cuối (hoặc là vị trí nhỏ nhất hoặc lớn nhất trong số tất cả các con bò).

Khi di chuyển một con bò, ông có thể chỉ định nó di chuyển đến bất kỳ vị trí số nguyên nào chưa được chiếm, miễn là tại vị trí mới này, nó không còn là điểm cuối nữa. Quan sát rằng theo thời gian, các loại di chuyển này thường kéo các con bò lại gần nhau hơn.

Yêu cầu: Xác định số lần di chuyển tối thiểu và tối đa mà Farmer John cần để nhóm các con bò lại với nhau ở các vị trí liên tiếp.

Input

• Dòng đầu tiên chứa hai số nguyên \(N (3 ≤ N ≤ 100000)\).

• Dòng thứ hai chứa \(N\) số nguyên \(x_1,x,…,x_N\) (\(1 ≤ x_i ≤ 10^9, x_i\) là vị trí con bò thứ \(i\)).

Output

• Dòng 1: Ghi số lần di chuyển tối thiểu tìm được.

• Dòng 2: Ghi số lần di chuyển tối đa tìm được.

Sample Input

3
7 4 9

Sample Output

1
2

Giải thích:

• Số lần di chuyển tối thiểu là 1 – nếu Farmer John di chuyển con bò ở vị trí 4 đến vị trí 8, thì các con bò sẽ nằm ở các vị trí liên tiếp 7, 8, 9.

• Số lần di chuyển tối đa là 2. Ví dụ, con bò ở vị trí 9 có thể được di chuyển đến vị trí 6, sau đó con bò ở vị trí 7 có thể được di chuyển đến vị trí 5.