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.

INPUT

Dòng đầu tiên ghi sô nguyên dương ~N~ (~2 \le N \le 10^5~), là số lượng đội tuyền thẻ thao.

Trong ~N~ dòng tiếp theo: Môi dòng ghi ~2~ sô nguyên ~m_i~ và ~v_i~ (~0 ≤ m_i, v_i ≤ 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.

SUBTASKS

SAMPLE INPUT

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

SAMPLE OUTPUT

11

Có ~8~ đội, với tổng sức lần lượt là 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~. Hãy tính số dư của ~2^{3^N}~ khi chia cho ~5~.

INPUT

Số nguyên dương ~N~ (~1 \le N \le 10^9~).

OUTPUT

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

SUBTASKS

SAMPLE INPUT

2

SAMPLE OUTPUT

2

~3^2 = 9~, ~2^9 = 512~, ~512~ chia ~5~ dư ~2~.

Cho một dãy ~N~ số nguyên ~a_0, a_1, ..., a_{N - 1}~. Khoảng cách giữa hai số ~a_i~ và ~a_j~ (~0 \le i, j \le 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ố bằng nhau, in ra ~-1~.

INPUT

Dòng đầu tiên chứa nguyên dương ~N~ (~2 \le N \le 10^5~).

Dòng thứ hai ghi ~N~ số nguyên ~a_0, a_1, ..., a_{N - 1}~ (~-10^9 \le a_i \le 10^9~).

OUTPUT

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

SUBTASKS

SAMPLE INPUT

5
7 2 3 2 7

SAMPLE OUTPUT

2

Dãy ~[7, 2, 3, 2, 7]~ có hai cặp số bằng nhau:

• ~7~ ở vị trí ~O~ 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~ 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, ..., i_k~ mà ~H_{i_1} > H_{i_2} > H_{i_k}~.

INPUT

Dòng đầu tiên chứa nguyên dương ~N~ (~1 \le N \le 10^5~).

~N~ dòng tiếp theo, mỗi dòng ghi 2 số nguyên dương ~D_i, 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~.

OUTPUT

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

SUBTASKS

SAMPLE INPUT

4
2 3
3 2
2 2
1 3

SAMPLE OUTPUT

3

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~.