Tất cá các thành phố của Lineland đều năm trên trục tọa độ Ox. Do đó, mỗi thành phố được liên kết với vị trí xi - tọa độ trên trục Ox. Không có hai thành phố được đặt tại một điểm. Cư dân Lineland thích gửi thư cho nhau. Một người chỉ có thể gửi thư nếu người nhận sống ở một thành phố khác. Chi phí gửi thư chính xác bằng khoảng cách giữa thành phố của người gửi và thành phố của người nhận. Đối với mỗi thành phố, hãy tính hai giá trị mini và maxi, trong đó mini là chi phí tối thiểu để gửi thư từ thành phố thứ i đến một thành phố khác và maxi là chi phí tối đa để gửi thư từ thành phố thứ i đến một số thành phố khác.

Định dạng đầu vào: Dòng đầu tiên là số nguyên dương n. Dòng thứ hai chứa chuỗi n số nguyên khác nhau x1, x2,.... xn (-10^9 <= xi <=10^9), trong đó xi là tọa độ x của thành phố thứ i. Tất cả các xi là khác biệt và theo thứ tự tăng dần.

Ràng buộc: 2 ≤ n ≤ 10^6; -10^9 ≤ xi ≤ 10^9

Input:

4
-5 -2 2 7

Output:

3 12
3 9
4 7
5 12

Một nông dân đi thu hoạch chè tại đồi chè Tân Cương. Ông mang theo một chiếc gùi có sức chứa tối đa là W kg. Có N luống chè, luống thứ i có tổng khối lượng là wi kg và có tổng giá trị là vi đồng. Do chè có thể hái lẻ tẻ, ông có thể hái một phần của luống chè (ví dụ lấy 1 nửa khối lượng thì được 1 nửa giá trị).

Hãy tính tổng giá trị lớn nhất ông có thể thu được.

Dữ liệu vào:

Dòng 1: Hai số nguyên N và W (1 <= N <= 10^5, 1 <= W <= 10^9).

N dòng tiếp theo: Mỗi dòng chứa hai số nguyên vi và wi (1 <= vi, wi <= 10^6).

Kết quả ra: Tổng giá trị lớn nhất có thể thu được, in ra phần nguyên.

Ví dụ:

Input:

3 50
60 10
100 20
120 30

Output:

240

(Lấy toàn bộ luống 1 và 2, lấy 2/3 luống 3).

Tại Học Công Nghệ có 1 phòng máy tính. Có N lớp học muốn đăng ký sử dụng phòng máy này trong ngày. Lớp thứ i muốn bắt đầu vào thời điểm Si và kết thúc vào thời điểm Fi. Phòng máy chỉ phục vụ được 1 lớp tại 1 thời điểm. Hãy tính số lượng lớp học nhiều nhất có thể được xếp lịch sử dụng phòng máy.

Dữ liệu vào:

Dòng 1: Số nguyên N (1 <= N <= 10^5).

N dòng tiếp theo: Mỗi dòng chứa 2 số nguyên Si và Fi (0 <= Si < Fi <= 10^9).

Kết quả ra: Số lượng lớp học tối đa.

Ví dụ:

Input:

6
1 2
3 4
0 6
5 7
8 9
5 9

Output:

4

(Chọn các lớp có thời gian: [1,2], [3,4], [5,7], [8,9]).

Giờ ra chơi, N học sinh đứng thành một hàng ngang. Học sinh thứ i có chiều cao là Hi. Thầy giáo muốn xếp lại hàng sao cho tổng độ chênh lệch chiều cao giữa các học sinh đứng cạnh nhau là lớn nhất. (Tổng = |H1 - H2| + |H2 - H3| + ... + |H{N-1} - H_N|).

Dữ liệu vào:

Dòng 1: Số nguyên N (2 <= N <= 10^5).

Dòng 2: N số nguyên Hi (1 <= Hi <= 10^9).

Kết quả ra: Tổng độ chênh lệch lớn nhất.

Ví dụ:

Input:

4
1 2 4 8

Output:

16