Đầu xuân năm mới, Trung tâm Codedream đang muốn tổ chức 1 buổi tụ họp để ăn tiệc.

Có N giáo viên ở tọa độ ~A_i~ ~(1 ≤ A_i ≤ n)~, mỗi giáo viên chỉ có thể đi sang các khu vực lân cận là ~A_i + 1~ hoặc ~A_i - 1~ hoặc ko di chuyển (vẫn có thể đi đến điểm ~0~ hoặc ~n~+1 nếu GV đó có tọa độ ~1~ hoặc ~n~). Do đó Sếp Ngát đã nghĩ ra 1 cách tổ chức đặc biệt đó là cho mọi người tụ họp tại ít địa điểm khác nhau nhất hoặc chia ra nhiều địa điểm nhất có thể để tổ chức tất niên.

VD ~A = [1,2,4,4]~ thì có thể di chuyển thành ~[0,2,3,4]~, ~[2,2,3,4]~, …

Chúng ta phải tìm ra số địa điểm ít nhất và nhiều nhất mình có thể để trung tâm có 1 cái tết thật êm ấm.

Yêu cầu

Hãy tìm số địa điểm ít nhất và nhiều nhất có thể tổ chức tiệc.

Input

• Dòng 1 chứa số nguyên dương ~n~ ~(1≤n≤10^6)~
• Dòng 2 chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1≤a_i≤n)~

Output

Một dòng duy nhất chứa 2 số nguyên là số địa điểm ít nhất và nhiều nhất.

Sample Input 1

9
1 1 4 4 4 4 8 8 8

Sample Output 1

3 8

Sample Input 2

7
4 3 7 1 4 3 3

Sample Output 2

3 6

Subtask

• Có 50% số test ứng với 50% số điểm có ~n≤10^3~;
• 50% số test còn lại tương ứng với 50% số điểm không có giới hạn gì thêm.