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 điệ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.

Input

• Dòng đầu tiên ghi số nguyên dương \(N\) \((2 \leq N \leq 10^5)\) là số lượng đội tuyển thể thao.
• Trong \(N\) dòng tiếp theo, mỗi dòng ghi hai số nguyên \(m_i\) và \(v_i\) \((0 \leq m_i, v_i \leq 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.

Output

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

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \leq 100\).
• Subtask \(2\) (\(50\%\) số điểm): không có ràng buộc gì thêm.

Examples

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

11

Cho số nguyên dương \(N\). Hãy tính số dư của \(2^{3^{N}}\) khi chia cho \(5\).

Input

• Dòng đầu tiên ghi số nguyên dương \(N\) \((1 \leq N \leq 10^9)\).

Output

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

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N \leq 5\).
• Subtask \(2\) (\(50\%\) số điểm): không có ràng buộc gì thêm.

Examples

2

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 \leq i, j \leq N-1, i \neq j)\) được định nghĩa là \(|i - j|\). Tìm khoảng cách ngắn 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\).

Input

• Dòng đầu tiên ghi một số nguyên dương \(N\) \((2 \leq N \leq 10^5)\).
• Dòng thứ hai ghi \(N\) số nguyên \(a_0, a_1, \dots, a_{N-1}\) \((-10^9 \leq a_i \leq 10^9)\).

Output

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

Scoring

• Subtask \(1\) (\(80\%\) số điểm): \(N \leq 10^3\) và \(-10^5 \leq a_i \leq 10^5\) với \(0 \leq i \leq N - 1\).
• Subtask \(2\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Examples

5
7 2 3 2 7

2

Cho \(N\) hình chữ nhật, mỗi hình chữ nhật \(H\) có chiều dài \(D_H\) và chiều rộng \(R_H\).

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_AR_A > D_BR_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_AR_A = D_BR_B\) và \(D_A > D_B\).

Hãy tìm độ dài của dãy giảm 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, \dots, i_k\) mà \(H_{i1} > H_{i2} > \dots > H_{ik}\).

Input

• Dòng đầu tiên ghi số lượng hình chữ nhật \(N\) \((1 \leq N \leq 10^5)\).
• \(N\) dòng tiếp theo, mỗi dòng ghi 2 số nguyên dương \(D_i, R_i\) \((1 \leq D_i, R_i \leq 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\).

Output

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

Scoring

• Subtask \(1\) (\(70\%\) số điểm): \(N \leq 10^3\).
• Subtask \(2\) (\(30\%\) số điểm): không có ràng buộc gì thêm.

Examples

4
2 3
3 2
2 2
1 3

3