Huấn luyện viên Bình quản lý ~N~ đội tuyển thể thao, đội thứ ~i~ có hai thông số: sức bền ~m_i~ và sức mạnh ~v_i~. Để đánh giá toàn diện, ông Bình tính tổng sức ~T_i~ của mỗi đội là ~m_i + v_i~. Sau khi tính tất cả các giá trị ~T_i~, ông muốn biết chênh lệch giữa đội có tổng sức lớn nhất và đội có tổng sức bé nhất.

Yêu cầu

Tính chênh lệch giữa đội có tổng sức lớn nhất và đội có tổng sức bé nhất.

Dữ liệu đầu vào

Gồm ~N + 1~ dòng:

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(2 \le N \le 10^5)~ là số lượng đội tuyển thể thao.
• ~N~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~m_i~ và ~v_i~ ~(0 \le m_i, v_i \le 10^9)~ lần lượt là thông số sức bền và sức mạnh của mỗi đội tuyển.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là kết quả của bài toán.

Ràng buộc dữ liệu

• 50% số test có ~N \le 100~.
• 50% số test có ~N \le 10^5~.

Ví dụ

Ví dụ 1

INPUT

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

OUTPUT

11

Giải thích: Có ~8~ đội, với tổng sức lần lượt là ~4 + 6 = 10~, ~1 + 3 = 4~, ~2 + 5 = 7~, ~4 + 2 = 6~, ~3 + 3 = 6~, ~7 + 2 = 9~, ~8 + 1 = 9~ và ~7 + 8 = 15~, nên chênh lệch là ~15 - 4 = 11~.

Cho số nguyên dương ~N~.

Yêu cầu

Tính số dư của ~2^{3^N}~ khi chia cho ~5~.

Dữ liệu đầu vào

Gồm một dòng chứa số nguyên dương ~N~ ~(1 \le N \le 10^9)~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là kết quả của bài toán.

Ràng buộc dữ liệu

• 50% số test có ~N \le 5~.
• 50% số test còn lại không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

2

OUTPUT

2

Giải thích: ~3^2 = 9~, ~2^9 = 512~, ~512~ chia ~5~ dư ~2~.

Cho một dãy ~N~ số nguyên ~a_0, a_1, \ldots, a_{N-1}~. Khoảng cách giữa hai số ~a_i~ và ~a_j~ ~(0 \le i, j \le N - 1; i \ne j)~ được định nghĩa là ~|i - j|~. Tìm khoảng cách nhỏ nhất giữa hai số bằng nhau trong dãy, nếu không có hai số nào bằng nhau, in ra ~-1~.

Yêu cầu

Tìm khoảng cách nhỏ nhất giữa hai số bằng nhau trong dãy.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(2 \le N \le 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên ~a_0, a_1, \ldots, a_{N-1}~ ~(-10^9 \le a_i \le 10^9)~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là kết quả của bài toán.

Ràng buộc dữ liệu

• 80% số test có ~N \le 10^3~ và ~-10^5 \le a_i \le 10^5~ với ~0 \le i \le N-1~.
• 20% số test còn lại không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

5
7 2 3 2 7

OUTPUT

2

Giải thích: Dãy ~7, 2, 3, 2, 7~ có hai cặp số bằng nhau:

• ~7~ ở vị trí ~0~ và ~4~, khoảng cách ~4~;
• ~2~ ở vị trí ~1~ và ~3~, khoảng cách ~2~;

Nên kết quả của bài toán là ~2~.

Cho ~N~ hình chữ nhật, mỗi hình chữ nhật ~H_i~ có chiều dài ~D_i~ và chiều rộng ~R_i~. Hình chữ nhật ~A~ được gọi là lớn hơn hình chữ nhật ~B~, ký hiệu ~A > B~ nếu:

• Hoặc diện tích hình chữ nhật ~A~ lớn hơn diện tích hình chữ nhật ~B~, tức là ~D_A \times R_A > D_B \times R_B~;
• Hoặc diện tích hình chữ nhật ~A~ bằng diện tích hình chữ nhật ~B~ và chiều dài hình chữ nhật ~A~ lớn hơn chiều dài hình chữ nhật ~B~, tức là ~D_A \times R_A = D_B \times R_B~ và ~D_A > D_B~.

Yêu cầu

Hãy tìm độ dài của dãy giảm dần dài nhất (không cần liên tiếp) các hình chữ nhật. Tức là tìm số ~k~ lớn nhất sao cho tồn tại dãy các chỉ số ~i_1, i_2, \ldots, i_k~ mà ~H_{i_1} > H_{i_2} > \ldots > H_{i_k}~.

Dữ liệu đầu vào

Gồm ~N + 1~ dòng:

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(1 \le N \le 10^5)~ là số lượng hình chữ nhật.
• ~N~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~D_i~ và ~R_i~ ~(1 \le D_i, R_i \le 10^9)~ lần lượt là chiều dài và chiều rộng của hình chữ nhật thứ ~i~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là kết quả của bài toán.

Ràng buộc dữ liệu

• 70% số test có ~N \le 10^3~.
• 30% số test còn lại không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

4
2 3
3 2
2 2
1 3

OUTPUT

3

Giải thích: Các hình chữ nhật: ~(2, 3)~, ~(3, 2)~, ~(2, 2)~, ~(1, 3)~. Dãy giảm dần dài nhất với chỉ số tăng dần: ~(2, 3)~ (chỉ số ~0~) ~\rightarrow~ ~(2, 2)~ (chỉ số ~2~) ~\rightarrow~ ~(1, 3)~ (chỉ số ~3~), với diện tích ~6 \rightarrow 4 \rightarrow 3~, độ dài ~3~.