Contest giao lưu Tin học trẻ 2024 - Lần thứ Hai (Bảng B1)

Một dãy chia hết là một dãy các số đôi một phân biệt \(a_1, a_2, \dots, a_k\) sao cho với mọi \(i\):

• \(L \le a_i \le R\).
• \(a_{i+1}\) chia hết cho \(a_i\) nếu \(i < k\).

Bạn được cho hai số nguyên dương \(L, R\), yêu cầu:

• Xác định độ dài của dãy chia hết dài nhất (tìm \(k\) lớn nhất có thể).
• Trả lời xem có bao nhiêu dãy có độ dài như vậy.

Input

• Hai số nguyên dương \(L, R\) trên hai dòng (\(1 \le L \le R \le 10^{18}\)).

Output

• Hai số nguyên dương cách nhau một dấu cách: số lớn nhất có thể và số dãy có độ dài \(k\). Vì kết quả có thể rất lớn nên chỉ cần in ra \(9\) chữ số cuối của kết quả.

Example

3
16

3 2

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(R < 3 \times L\).
• Subtask \(2\) (\(30\%\) số điểm): \(R < 5 \times L\).
• Subtask \(3\) (\(20\%\) số điểm): \(R \le 1000\).
• Subtask \(4\) (\(20\%\) số điểm): Không có giới hạn gì thêm.

Nhân đang tập đếm các số \(1, 2, 3, 4, 5, \dots\) Nhận thấy việc này quá dễ, cộng với việc vừa mới học được phép nhân, Nhân quyết định đếm các số chính phương (là những số bằng một số nguyên nhân với chính nó) và viết chúng ra giấy và thu được một dãy dài có các số đầu tiên là \(149162536\dots\) Nhân muốn biết chữ số thứ \(n\) của dãy là bao nhiêu. Các bạn hãy tính giúp Nhân nhé.

Input

• Một số nguyên dương duy nhất \(n\) (\(1 \le n \le 10^{18}\)).

Output

• Chữ số thứ \(n\) của dãy.

Example

10

4

Subtask

• Subtask 1 (\(30\%\) số điểm): \(n \le 1000\).
• Subtask 2 (\(30\%\) số điểm): \(n \le 10^{12}\).
• Subtask 3 (\(40\%\) số điểm): Không có giới hạn gì thêm.

Có \(n\) người tham gia một cuộc thi. Người thứ \(i\) có chỉ số sức mạnh là \(a_i\). Ban tổ chức muốn thực hiện ghép hai người thành một đội để thu được \(\lfloor\frac{n}{2}\rfloor\) đội thi (nếu \(n\) lẻ thì sẽ có một người bị loại) sao cho chênh lệch sức mạnh tối đa của hai đội bất kỳ là nhỏ nhất. Biết rằng, chỉ số sức mạnh của một đội gồm hai người \((u, v)\) sẽ là \(a_u + a_v\). Hãy giúp ban tổ chức tìm ra cách ghép tối ưu.

Input

• Dòng đầu tiên gồm một số nguyên dương \(n \le 3 \times 10^5\) – số người trong cuộc thi.
• Dòng tiếp theo gồm \(n\) số nguyên \(0 \le a_i \le 10^9\).

Output

• Một dòng duy nhất gồm chênh lệch sức mạnh nhỏ nhất có thể thu được.

Example

6
1 1 1 2 2 3

1

Scoring

• Subtask 1 (\(30\%\) số điểm): \(n\) chẵn.
• Subtask 2 (\(30\%\) số điểm): \(n \le 1000\) và \(n\) lẻ.
• Subtask 3 (\(20\%\) số điểm): \(a_i \le 1\).
• Subtask 4 (\(20\%\) số điểm): \(n\) lẻ.

Bạn được cho một dãy \(A = [a_1, a_2, \dots, a_n]\). Xét \(B\) là dãy gồm các trung vị của các đoạn con liên tiếp của \(A\), hãy tính trung vị của \(B\).

Nhắc lại, trung vị của một dãy đã được sắp xếp \(x_1, x_2, \dots, x_k\) là \(x_{\lfloor \frac{k+1}{2} \rfloor}\).

Input

• Dòng đầu tiên chứa một số nguyên dương \(1 \le n \le 10^5\) – số phần tử của dãy \(A\).
• Dòng tiếp theo gồm \(n\) số nguyên dương \(1 \le a_i \le 10^9\).

Output

• Một dòng duy nhất gồm kết quả bài toán.

Example

4
1 2 3 4

2

4
1 1 2 2

1

4
4 3 2 1

2

Subtask

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 1000\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 5000\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 20000\).
• Subtask \(4\) (\(20\%\) số điểm): \(n \le 50000\).
• Subtask \(5\) (\(10\%\) số điểm): \(n \le 10^5\) và các phần tử của dãy \(A\) chỉ có \(2\) giá trị khác nhau.
• Subtask \(6\) (\(10\%\) số điểm): Không có ràng buộc gì thêm.