Xâu \(x\) được gọi là lớn hơn xâu \(y\) nếu xâu \(y\) là đoạn đầu của xâu \(x\) hoặc xét kí tự đầu tiên khác nhau thì kí tự của xâu \(x\) lớn hơn kí tự của xâu \(y\).

Để luyện tập về việc so sánh hai xâu, Hồng đã tạo ra bài toán sau: Từ hai số nguyên dương \(a,b (a < b)\), tạo ra một dãy số gồm \(b - a + 1\) số: \(a, a + 1, ... , b\). Sau đó, sắp xếp lại các số theo thứ tự từ điển (coi mỗi số là một xâu và sắp xếp tăng dần) bằng các thao tác như sau: Mỗi lần chọn
và lấy ra một số trong dãy rồi chèn lại vào dãy ở vị trí bất kì.

Ví dụ, nếu \(a = 9, b = 11\) ta có dãy số gồm \(3\) số \(9, 10, 11\), dãy số được sắp xếp theo thứ tự từ điển là \(10, 11, 9\) và cần ít nhất một thao tác (rút số \(9\) khỏi dãy và chèn vào cuối dãy).

Yêu cầu: Cho hai số nguyên dương \(a, b (a < b)\), hãy tính số thao tác ít nhất để sắp xếp các số \(a, a + 1, ... , b\) theo thứ tự từ điển.

Input

• Vào từ thiết bị vào chuẩn gồm một dòng chứa hai số nguyên dương \(a, b (a < b \le 10^9)\)

Output

• Ghi ra thiết bị ra chuẩn gồm một dòng chứa một số nguyên là số thao tác ít nhất để sắp xếp các số \(a, a + 1, ... , b\) theo thứ tự từ điển.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(b - a = 1\);
• Subtask \(2\) (\(20\%\) số điểm): \(b - a \le 10\);
• Subtask \(3\) (\(30\%\) số điểm): \(b − a \le 1000\);
• Subtask \(4\) (\(30\%\) số điểm): \(b − a \le 10^5\);

Example

9 11

1

Hồng đã soạn được \(n\) bài tập Tin học, bài thứ ݅\(i(1 \le i \le ݊n)\) có độ khó là số nguyên dương \(c_i\). Hồng được cô giáo yêu cầu gửi \(m\) bài tập lên hệ thống luyện tập trực tuyến để tập huấn cho một nhóm các em học sinh khóa dưới. Nếu \(m < n\), khi đó, Hồng phải loại bỏ \(n - m\) bài tập, ngược lại nếu \(m > n\) thì Hồng phải soạn thêm \(m - n\) bài tập với độ khó là số nguyên dương. Khi đưa lên hệ thống \(m\) bài tập, Hồng sẽ sắp xếp các bài theo độ khó tăng dần, gọi \(d\) là chênh lệch độ khó lớn nhất của hai bài tập liên tiếp. Hồng mong muốn giá trị \(d\) nhỏ nhất có thể.

Yêu cầu: Cho \(n\) bài tập với độ khó là ܿ\(c_1, c_2, ..., c_n\) và số \(m\), hãy tìm giá trị \(d\) nhỏ nhất.

Input

Vào từ thiết bị vào chuẩn:

• Dòng đầu gồm hai số nguyên dương ݊\(n, m (2 \le m, n \le 10^5; m \ne n)\);
• Dòng thứ hai gồm ݊ số nguyên dương \(c_1, c_2, ..., c_n\) \((c_i \le 10^9, 1 \le i \le n)\).

Output

• Ghi ra thiết bị ra chuẩn gồm một dòng chứa một số nguyên \(d\) tìm được.

Example

5 4
8 5 9 10 10

1

3 4
8 6 9

1

Một bài toán khó trong danh sách các bài mà Hồng lựa chọn để tập huấn cho các em học sinh khóa
dưới như sau:

Cho hai số nguyên dương \(n, t\),cần tìm một bộ gồm ít số nguyên dương nhất, giả sử bộ tìm được gồm \(k\) số nguyên dương \(a_1, a_2,..., a_k\) thì:

Yêu cầu: Cho \(2\) số nguyên dương \(n, t\), hãy tìm số nguyên dương \(k\) thoả mãn.

Input

• Vào từ thiết bị vào chuẩn gồm một dòng chứa hai số nguyên \(n, t (n, t \le 1000)\)

Output

• Ghi ra thiết bị ra chuẩn gồm một dòng chứa số nguyên \(k\) là số lượng số ít nhất để tồn tại bộ gồm \(k\) số nguyên dương thoả mãn, nếu không tồn tại ghi số \(-1\).

Example

4 1

2

Công ty HP vừa thiết kế một loại robot thông minh mới. Để đánh giá khả năng tự vận hành của robot, người ta tạo ra một bức tường từ ݊ cột các khối lập phương, các cột đặt cạnh nhau, bề dày bức tường là 1, độ cao cột thứ \(i\) là ܽ\(a_i\) (do ܽ\(a_i\) khối lập phương tạo lên). Có ݉\(m\) robot tham gia thử nghiệm. Trước tiên người ta chia ݊\(n\) cột thành ݉\(m\) đoạn bằng ݉\(m − 1\) điểm cắt ݇\(k_1, ݇k_2, . . , ݇k_{m-1} (݇k_0 = 0 < k_1 < ... < ݇k_{m-1} < k_m = n)\). Robot thứ ݅ được giao nhiệm vụ xếp lại đoạn từ cột ݇\(k_{i-1} + 1\) đến cột ݇\(k_i\) sao cho các cột trong đoạn có độ cao bằng nhau. Robot chỉ có thể thực hiện một trong hai loại thao tác, mỗi thao tác mất 1 đơn vị thời gian.

• Thao tác 1: Lấy khối trên cùng của một cột trong đoạn được giao để bỏ đi;
• Thao tác 2: Lấy một khối mới, đặt khối đó lên trên cùng của một cột trong đoạn được giao.

Thời gian kết thúc thử nghiệm là thời gian mà robot cuối cùng hoàn thành xong nhiệm vụ.

Yêu cầu: Cho \(a_1, a_2, ..., a_n\) và ݉\(m\). Hãy tìm \(m− 1\) điểm cắt để chia cột thành ݉\(m\) đoạn sao cho thời gian thử nghiệm là nhanh nhất, biết các robot đều thực hiện các thao tác tối ưu.

Input

Vào từ thiết bị nhập chuẩn:

• Dòng đầu chứa hai số nguyên \(n, m\);
• Dòng thứ hai gồm ݊\(n\) số nguyên không âm \(a_1, a_2, ..., a_n (a_i \le 10^6)\)

Output

• Ghi ra thiết bị ra chuẩn một dòng chứa một số nguyên là thời gian ít nhất để thử nghiệm.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(m = 1; n \le 10\);
• Subtask \(2\) (\(25\%\) số điểm): \(m = 2; n \le 1000\);
• Subtask \(3\) (\(25\%\) số điểm): ݉\(m \le n; n \le 100\);
• Subtask \(4\) (\(25\%\) số điểm): ݉\(m\le n; n \le 1000\).

Example

6 2
1 1 2 3 4 3

1

.

Bài 3: Xâu con

.

.

Bài 4: Cắt bánh

.