Cho một dãy số ~A~ gồm ~N~ số nguyên ~A_1, A_2, \ldots, A_N~. Hãy tìm dãy con tăng dài nhất thuộc dãy ~A~.

Một dãy con tăng độ dài ~k~ thuộc dãy ~A~ có dạng là dãy ~A_{i_1}, A_{i_2}, A_{i_3}, \ldots, A_{i_{k - 1}}, A_{i_k}~ với

• ~1 \leq i_1 < i_2 < \ldots < i_k \leq N~;
• ~A_{i_1} < A_{i_2} < \ldots < A_{i_k}~.

Input

• Dòng thứ nhất gồm một số nguyên dương ~N~ - kích thước dãy ~A~ (~1 \leq N \leq 10^3~)
• Dòng thứ hai gồm ~N~ số nguyên ~A_1, A_2, \ldots, A_N~ (~|A_i| \leq 10^3~).

Output

• Dòng thứ nhất in ra độ dài của dãy con tăng dài nhất của dãy ~A~.
• Dòng thứ hai in ra các vị trí trong dãy ~A~ của các phần tử thuộc dãy con nói trên, các số tăng dần và cách nhau ít nhất ~1~ khoảng trắng. Nếu có nhiều dãy con thoả mãn, in ra các vị trí có thứ tự từ điển nhỏ nhất.

Sample Test 1

Input:

8
2 -1 1 4 1 -5 2 3

Output:

4
2 3 7 8

Sample Test 2

Input:

5
1 2 -10 0 3

Output

3
1 2 5

Một phòng họp do bạn quản lý được ~N~ cuộc họp đặt lịch. Cuộc họp thứ ~i~ có thời gian bắt đầu là ~A_i~ và kết thúc tại thời điểm ~B_i~ (~A_i < B_i~). Hai cuộc họp không thể cùng đồng thời diễn ra, nói cách khác cuộc họp thứ ~j~ chỉ có thể được bố trí sau cuộc họp thứ ~i~ nếu ~B_j \leq A_i~.

Là người quản lý phòng họp, bạn hãy sắp xếp lịch để bố trí nhiều cuộc họp diễn ra nhất có thể.

Input

• Dòng thứ nhất gồm một số nguyên dương ~N~ (~1 \leq N \leq 10^3~).
• Trong ~N~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~A_i~ và ~B_i~ (~A_i < B_i \leq 10^3~).

Output

• In ra số lượng cuộc họp nhiều nhất có thể bố trí.

Sample Test

Input:

5
1 2
3 7
2 5
4 6
6 8

Output:

3

Note:

• Chọn cuộc họp ~1, 3, 5~.

Một phòng họp do bạn quản lý được ~N~ cuộc họp đặt lịch. Cuộc họp thứ ~i~ có thời gian bắt đầu là ~A_i~, kết thúc tại thời điểm ~B_i~ và trả tiên thuê là ~C_i~ (~A_i < B_i~). Hai cuộc họp không thể cùng đồng thời diễn ra, nói cách khác cuộc họp thứ ~j~ chỉ có thể được bố trí sau cuộc họp thứ ~i~ nếu ~B_j \leq A_i~.

Là người quản lý phòng họp, bạn hãy sắp xếp lịch bố trí các cuộc họp để thu được lợi nhuận lớn nhất có thể.

Input

• Dòng thứ nhất gồm một số nguyên dương ~N~ (~1 \leq N \leq 10^3~).
• Trong ~N~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên dương ~A_i, B_i, C_i~ (~A_i < B_i; B_i, C_i \leq 10^3~).

Output

• In ra lợi nhuận lớn nhất có thể thu được.

Sample Test

Input:

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

Output:

7

Note:

• Chọn cuộc họp ~1, 2, 5~.

Cho một dãy số ~A~ gồm ~N~ số nguyên ~A_1, A_2, \ldots, A_N~. Hãy tìm dãy con đổi dấu dài nhất thuộc dãy ~A~.

Một dãy con đổi dấu độ dài ~k > 1~ thuộc dãy ~A~ có dạng là dãy ~A_{i_1}, A_{i_2}, A_{i_3}, \ldots, A_{i_{k - 1}}, A_{i_k}~ với các điều kiện sau:

• Các phần tử liên tiếp khi so sánh lần lượt "đổi dấu" liên tục: ~A_{i_1} < A_{i_2}, A_{i_2} > A_{i_3}, A_{i_3} < A_{i_4}, \ldots~ hoặc ~A_{i_1} > A_{i_2}, A_{i_2} < A_{i_3}, A_{i_3} > A_{i_4}, \ldots~;
• Các phần tử có chỉ số tăng dần và cách nhau ít nhất ~L~ đơn vị: ~i_2 - i_1 \geq L~, ~i_3 - i_2 \geq L, \ldots, i_k - i_{k - 1} \geq L~;
• Các phần tử liên tiếp có chênh lệch không quá ~U~: ~|A_{i_1} - A_{i_2}| \leq U, |A_{i_2} - A_{i_3}| \leq U, \ldots, |A_{i_{k - 1}} - A_{i_k}| \leq U~.

Dãy gồm một phần tử cũng được coi là một dãy đổi dấu.

Input

• Dòng thứ nhất gồm 3 số nguyên dương ~N, L, U~ (~L < N \leq 10^3~, ~U \leq 10^3~)
• Dòng thứ hai gồm ~N~ số nguyên ~A_1, A_2, \ldots, A_N~ (~|A_i| \leq 10^3~).

Output

• In ra độ dài của dãy con đan dấu dài nhất.

Sample Test 1

Input:

8 2 3
2 -1 1 4 1 -5 2 3

Output:

3

Note

• Chọn dãy con ~-1, 1, 3~ (vị trí ~2, 5, 8~).

Một đêm nọ, một tên trộm nọ quyết định đột nhập vào một siêu thị nọ. Siêu thị có ~N~ đồ vật, vật thứ ~i~ có trọng lượng ~A_i~, giá trị ~B_i~. Tên trộm mang theo một cái túi chứa được trọng lượng tối đa ~W~. Hỏi tổng giá trị tối đa tên trộm có thể lấy được là bao nhiêu?

Input

• Dòng thứ nhất gồm hai số nguyên dương ~N~ và ~W~ (~1 \leq N, W \leq 10^3~).
• Trong ~N~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~A_i~ và ~B_i~ (~A_i, B_i \leq 10^3~).

Output

• In ra tổng giá trị lớn nhất có thể được lấy đi.

Sample Test

Input:

5 15
12 4
2 2
1 1
1 2
4 10

Output:

15

Cho một dãy số ~A~ gồm ~N~ số nguyên dương ~A_1, A_2, \ldots, A_N~ và một số nguyên dương ~S~. Hãy tìm ~1~ dãy con có tổng ~S~ thuộc dãy ~A~.

Một dãy con tổng ~S~ thuộc dãy ~A~ có dạng là dãy ~A_{i_1}, A_{i_2}, A_{i_3}, \ldots, A_{i_{k - 1}}, A_{i_k}~ với

• ~1 \leq i_1 < i_2 < \ldots < i_k \leq N~;
• ~A_{i_1} + A_{i_2} + \ldots + A_{i_k} = S~.

Input

• Dòng thứ nhất gồm hai số nguyên dương ~N~ và ~S~ (~N, S \leq 10^3~)
• Dòng thứ hai gồm ~N~ số nguyên dương ~A_1, A_2, \ldots, A_N~ (~A_i \leq 10^3~).

Output

• Nếu dãy con tổng ~S~ tổn tại, in ra các chỉ số trong ~A~ của phần tử thuộc dãy con đó. Nếu có nhiều dãy con thoả mãn thì in ra các chỉ số có thứ tự từ điển nhỏ nhất. Ngược lại, nếu không có dãy con thoả mãn thì in ra Does not exist.

Sample Test 1

Input:

5 7
1 3 5 9 3

Output:

1 2 5

Sample Test 2

Input:

4 17
1 3 5 7

Output:

Does not exist

Có ~N~ gói kẹo, gói thứ ~i~ chứa ~A_i~ viên kẹo. Hãy chia các gói thành ~2~ phần sao cho chênh lệch số viên kẹo giữa 2 phần là ít nhất.

Input

• Dòng thứ nhất gồm một số nguyên dương ~N~ (~1 \leq N \leq 100~).
• Dòng tiếp theo chứa ~N~ số ~A_1, A_2, \ldots, A_N~ (~A_i \leq 50~).

Output

• In ra chênh lệch nhỏ nhất số viên kẹo giữa ~2~ nhóm kẹo.

Sample Test 1

Input:

5
2 4 9 3 5

Output:

1

Cho 1 xâu nguồn ~X~ và một xâu đích ~F~. Bạn có thể thực hiện ba thao tác sau trên xâu ~X~:

• Chèn ~1~ kí tự vào sau kí tự thứ ~i~.
  • Ví dụ: ~abcd \rightarrow abecd~.
• Thay thế kí tự ở vị trí thứ ~i~ bằng kí tự C.
  • Ví dụ: ~abcd \rightarrow abce~.
• Xoá kí tự ở vị trí thứ ~i~.
  • Ví dụ: ~abcd \rightarrow abd~.

Tính số lượng thao tác ít nhất để biến đổi xâu ~X~ thành xâu ~F~.

Input

• Dòng thứ nhất chứa xâu ~X~.
• Dòng thứ hai chứa xâu ~F~.
• Hai xâu chỉ gồm các chữ cái thường và độ dài hai xâu không vượt quá ~10^3~.

Output

• In ra số lượng thao tác ít nhất.

Sample Test

Input:

abcd
bde

Output:

3

Cho ~2~ xâu ~A~ và ~B~. Tìm dãy con chung dài nhất của ~2~ xâu này.

Một dãy con của một xâu là xâu thu được sau khi xoá một số kí tự (có thể xoá ~0~ kí tự hoặc xoá toàn bộ kí tự) và giữ nguyên thứ tự của các kí tự còn lại.

Input

• Dòng thứ nhất chứa xâu ~A~.
• Dòng thứ hai chứa xâu ~B~.
• Hai xâu chỉ gồm các chữ cái thường và độ dài hai xâu không vượt quá ~10^3~.

Output

• In ra số lượng thao tác ít nhất.

Sample Test 1

Input:

bbus
uii

Output:

1

Sample Test 2

Input:

uapjhvvjlrilrkuleah
faoipjzllkluegle

Output:

9

Cho một xâu ~S~, hãy tìm số kí tự ít nhất cần thêm vào ~S~ để ~S~ trở thành xâu đối xứng.

Một xâu gọi là xâu đối xứng (palindrome) nếu xâu đó đọc từ trái sang phải hay từ phải sang trái đều như nhau.

Input

• Gồm một xâu S duy nhất chứa các kí tự thường (~|S| \leq 1000~).

Output

• In ra số lượng kí tự ít nhất cần thêm.

Sample Test 1

Input:

bbubbs

Output:

1