Chú chó chăn cừu

Bối cảnh

Chú chó chăn cừu tên One phát hiện ra rằng đàn cừu của mình luôn lang thang đến những nơi xa nhất trong trang trại! One cần sự giúp đỡ của bạn để dẫn chúng trở lại với nhau. Cánh đồng chính trong trang trại rất dài và hẹp - chúng ta có thể coi nó như một dãy số, trên đó một con cừu có thể chiếm một vị trí nguyên bất kỳ. Hiện tại, \(N\) con cừu đang ở các vị trí nguyên khác nhau, và One muốn chúng di chuyển để chiếm các vị trí liên tiếp (ví dụ, các vị trí \(3, 4, 5, 6, 7,\) và \(8\)).

Yêu cầu

Thật không may, các con cừu khá buồn ngủ, và One gặp khó khăn trong việc thu hút sự chú ý của chúng để làm cho chúng di chuyển. Tại bất kỳ thời điểm nào, chú chỉ có thể khiến một con cừu di chuyển nếu nó là một "đ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 cừu). Khi chú di chuyển một con cừu, chú có thể chỉ đạo nó di chuyển đến bất kỳ vị trí nguyên không có con cừu nào chiếm dụng miễn là tại vị trí mới này nó không còn là điểm cuối. Quan sát cho thấy theo thời gian, những di chuyển này có xu hướng đẩy các con cừu gần nhau hơn.

Hãy xác định số lượng di chuyển tối thiểu và tối đa có thể trước khi các con cừu được tập hợp vào \(N\) vị trí liên tiếp.

Input

Dòng đầu tiên của đầu vào chứa \(N (3≤N≤10^5)\). Mỗi dòng tiếp theo chứa vị trí nguyên của một con cừu, trong khoảng từ \(1\) đến \(10^9\).

Output

Dòng đầu tiên của đầu ra chứa số lượng di chuyển tối thiểu One cần thực hiện để tập hợp các con cừu lại với nhau. Dòng thứ hai của đầu ra chứa số lượng di chuyển tối đa mà One có thể thực hiện trước khi các con cừu được tập hợp lại với nhau.

Ràng buộc

Đề gốc không nêu ràng buộc riêng.

Ví dụ 1

Input

3
7
4
9

Output

1
2

Giải thích ví dụ

• Ví dụ 1:
  • Dữ liệu: 3, 7 4 9
  • Giải thích: Để tập hợp ba con cừu vào các vị trí liên tiếp, tối thiểu là cần 1 di chuyển (chuyển cừu từ 4 đến 8). Tối đa có thể thực hiện 2 di chuyển, ví dụ chuyển cừu từ 9 đến 6, rồi chuyển cừu từ 7 đến 5.

Số lượng di chuyển tối thiểu là \(1\) nếu One di chuyển con cừu ở vị trí \(4\) đến vị trí \(8\), thì các con cừu sẽ ở các vị trí liên tiếp \(7, 8, 9\). Số lượng di chuyển tối đa là \(2\). Ví dụ, con cừu ở vị trí \(9\) có thể được di chuyển đến vị trí \(6\), sau đó con cừu ở vị trí \(7\) có thể được di chuyển đến vị trí \(5\).

Thông tin học tập

• Buổi: B18
• Concepts: STL arrays, advanced array techniques, optional advanced topics
• Giới hạn kiến thức: B01-B18
• Time limit: 1 second
• Memory limit: 20 MB
• Point: 30