Cho hai mảng số nguyên không giảm A và B, mỗi mảng có độ dài n. Hãy gộp hai mảng này thành một mảng mới cũng theo thứ tự không giảm và in ra mảng kết quả.

Input

• Dòng đầu chứa số nguyên n (1 ≤ n ≤ 10^5).
• Dòng thứ hai chứa n số nguyên là các phần tử của mảng A (1 ≤ A_i ≤ 10^9).
• Dòng thứ ba chứa n số nguyên là các phần tử của mảng B (1 ≤ B_i ≤ 10^9).

Output

• In ra mảng đã gộp theo thứ tự không giảm: tất cả phần tử của A và B sắp xếp vào một mảng duy nhất.

Ví dụ

Input

3
1 3 4
1 2 3

Ouput

1 1 2 3 3 4

Cho một mảng số nguyên ~A~ có độ dài ~n~. Hãy đếm số lượng đoạn con liên tiếp (subarray) mà trong đó tất cả các phần tử đều khác nhau.

Input

• Dòng đầu chứa số nguyên ~n~ ~(1 \le n \le 10^5)~.
• Dòng tiếp theo chứa ~n~ số nguyên ~A_i~ ~(1 \le A_i \le 10^5)~.

Output

• Một số nguyên duy nhất — số lượng đoạn con mà tất cả phần tử trong đó là phân biệt.

Ví dụ

Input

4
1 2 1 2

Output

7

Thanhmay2005 có ~n~ cây nấm, cây nấm thứ ~i~ nặng ~A_i~. Hôm nay anh ấy muốn pha một lọ thuốc. Anh ấy có thể dùng một số lượng nấm bất kì cho một lọ thuốc nhưng hai cây nấm có cân nặng chênh lệch quá ~k~ không thể được dùng trong cùng lọ thuốc. Tối đa bao nhiêu cây nấm có thể được dùng để làm một lọ thuốc? (Thanhmay2005 muốn lọ thuốc của anh ấy mạnh nhất có thể).

Input

• Dòng đầu chứa hai số nguyên ~n~, ~k~ ~(1 \le n \le 10^5)~, ~(1 \le k \le 10^9)~.
• Dòng thứ hai chứa ~n~ số nguyên ~A_i~ ~(1 \le A_i \le 10^9)~.

Output

• Một số nguyên duy nhất — số lượng nấm tối đa Marisa có thể chọn để làm một chai thuốc thoả điều kiện.

Ví dụ

Input

6 6
1 2 5 7 9 10

Output

4

Cho mảng ~A~ gồm ~n~ phần tử nguyên phân biệt được sắp xếp theo thứ tự tăng dần. Hãy đếm số lượng cặp chỉ số ~(i, j)~ với ~i < j~ sao cho ~A_i + A_j = x~.

Input

• Dòng đầu chứa hai số nguyên ~n~, ~x~ ~(1 \le n \le 10^5)~, ~(1 \le A_i, x \le 10^9)~.
• Dòng thứ hai chứa ~n~ số nguyên phân biệt ~A_i~, sắp xếp theo thứ tự tăng dần.

Output

• Một số nguyên duy nhất — số lượng cặp ~(i, j)~ thoả mãn điều kiện.

Ví dụ

Input

5 6
1 2 3 4 5

Output

2

AliVu và banmkh62 đang chơi một trò chơi. Trên bàn có ~n~ tấm thẻ, mỗi tấm thẻ có một số nguyên. Hai người chơi luân phiên nhau. Trong mỗi lượt, người chơi có thể lấy tấm thẻ ngoài cùng bên trái hoặc ngoài cùng bên phải. Trò chơi kết thúc khi không còn tấm thẻ nào. Người có tổng điểm lớn hơn sẽ thắng. Vì AliVu và banmkh62 khá tham lam nên mỗi lượt chọn họ sẽ lấy tấm thẻ có số điểm lớn hơn trong hai tấm thẻ ngoài cùng. Hãy tính số điểm cuối cùng của AliVu và banmkh62.

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 1000)~ — số lượng tấm thẻ.
• Dòng thứ hai chứa ~n~ số nguyên ~a_i~ phân biệt ~(1 \le a_i \le 1000)~, giá trị trên mỗi tấm thẻ, được liệt kê từ trái sang phải.

Output

• In ra hai số nguyên: điểm của AliVu và điểm của banmkh62.

Ví dụ

Input

5
3 6 5 4 2

Output

10 10

TDH có một dãy số nguyên ban đầu gồm ~n~ số a[1..n].
Cậu ta viết lên bảng trắng theo thứ tự sau:

• Viết a1 vào bên trái bảng.
• Viết a2 vào bên phải của bảng.
• Viết a3 vào bên phải của a1.
• Viết a4 vào bên trái của a2.
• …

Cứ tiếp tục như vậy cho đến khi viết hết toàn bộ ~n~ số.

Ví dụ: với ~n = 5~, dãy ban đầu là a = [4, 6, 3, 2, 8].
Thứ tự viết lên bảng sẽ thành: [4, 3, 8, 2, 6].

Bây giờ, TDH đưa cho bạn chuỗi số đã viết trên bảng, hãy khôi phục lại dãy số ban đầu.

Input

• Dòng đầu tiên chứa một số nguyên ~n~ ~(1 \le n \le 9000)~ — độ dài chuỗi được viết trên bảng.
• Dòng thứ hai chứa ~n~ số nguyên ~b_1, b_2, …, b_n~ ~(1 \le b_i \le 10^9)~ — các số trên bảng.

Output

• In ra ~n~ số nguyên, chính là dãy ban đầu a.

Ví dụ

Input 1

7
3 4 5 2 9 1 1

Output 1

3 1 4 1 5 9 2

Input 2

11
8 4 3 1 2 7 8 7 9 4 2

Output 2

8 2 4 4 3 9 1 7 2 8 7

Trường của Nghialaptrinh tổ chức một cuộc thi lập trình. Có ~n~ sinh viên muốn tham gia, trong đó sinh viên thứ ~i~ có kỹ năng lập trình là ~a_i~.

Nhà trường muốn cuộc thi có càng nhiều sinh viên tham gia càng tốt. Tuy nhiên, sự chênh lệch kỹ năng giữa bất kỳ hai sinh viên nào trong nhóm không được vượt quá 5, nếu không sẽ bị mất cân bằng.

Vì vậy, ban tổ chức sẽ chọn một nhóm sinh viên sao cho chênh lệch lớn nhất giữa hai sinh viên bất kỳ trong nhóm ≤ 5.
Hãy giúp Nghialaptrinh biết số lượng sinh viên tối đa có thể tham gia cuộc thi.

Input

• Dòng đầu chứa số nguyên ~n~ ~(1 \le n \le 2 \times 10^5)~ — số sinh viên.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le 10^9)~, trong đó ~a_i~ là kỹ năng của sinh viên thứ ~i~.

Output

• In ra một số nguyên duy nhất — số lượng sinh viên tối đa có thể tham gia.

Ví dụ

Input 1

6
1 10 17 12 15 2

Output 1

3

Input 2

10
1337 1337 1337 1337 1337 1337 1337 1337 1337 1337

Output 2

10

Giải thích

• Ở ví dụ 1: ta có thể chọn nhóm sinh viên có kỹ năng [12, 15, 17], chênh lệch lớn nhất = 5.
• Ở ví dụ 2: tất cả có thể vào cùng một nhóm vì kỹ năng bằng nhau.

Bạn được cho hai mảng số nguyên, đã được sắp xếp không giảm. Với mỗi phần tử trong mảng thứ hai, hãy tìm số lượng phần tử trong mảng thứ nhất nhỏ hơn nó.

Input

• Dòng đầu chứa hai số nguyên ~n~, ~m~ ~(1 \le n, m \le 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_i~ ~(-10^9 \le a_i \le 10^9)~, các phần tử của mảng thứ nhất.
• Dòng thứ ba chứa ~m~ số nguyên ~b_i~ ~(-10^9 \le b_i \le 10^9)~, các phần tử của mảng thứ hai.

Cả hai mảng đều được sắp xếp theo thứ tự không giảm.

Output

• In ra ~m~ số nguyên, số thứ ~i~ biểu thị số lượng phần tử trong mảng thứ nhất nhỏ hơn ~b_i~.

Ví dụ

Input

6 7
1 6 9 13 18 18
2 3 8 13 15 21 25

Output

1 1 2 3 4 6 6

Bạn được cho hai mảng ~a~ và ~b~, đã được sắp xếp theo thứ tự không giảm. Hãy tìm số lượng cặp ~(i, j)~ sao cho ~a_i = b_j~.

Input

• Dòng đầu chứa hai số nguyên ~n~, ~m~ ~(1 \le n, m \le 10^5)~ — độ dài của mảng ~a~ và ~b~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_i~ ~(-10^9 \le a_i \le 10^9)~, các phần tử của mảng ~a~, theo thứ tự không giảm.
• Dòng thứ ba chứa ~m~ số nguyên ~b_j~ ~(-10^9 \le b_j \le 10^9)~, các phần tử của mảng ~b~, theo thứ tự không giảm.

Output

• In ra một số nguyên duy nhất — số lượng cặp ~(i, j)~ thoả mãn ~a_i = b_j~.

Ví dụ

Input

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

Output

11

Bạn được cho một mảng gồm ~n~ số nguyên ~a_i~. Một đoạn con liên tiếp ~a[l..r]~ ~(1 \le l \le r \le n)~ được gọi là tốt nếu tổng các phần tử trong đoạn này không vượt quá ~s~. Nhiệm vụ của bạn là tìm độ dài lớn nhất của một đoạn con tốt.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~, ~s~ ~(1 \le n \le 10^5, \; 1 \le s \le 10^{18})~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_i~ ~(1 \le a_i \le 10^9)~.

Output

• In ra một số nguyên duy nhất: độ dài lớn nhất của đoạn con tốt.
• Nếu không tồn tại đoạn con nào thoả mãn, in ra 0.

Ví dụ

Input

7 20
2 6 4 3 6 8 9

Output

4

Trong một buổi sinh hoạt học thuật ở UMT, các thành viên được giao nhiệm vụ làm sạch một tập dữ liệu đầu vào bị trùng lặp. Mỗi bạn được cấp một dãy số gồm ~n~ phần tử nguyên, đại diện cho các mã sinh viên do hệ thống ghi nhận (đôi khi bị lỗi lặp mã).

Để chuẩn bị cho một buổi phân tích tiếp theo, cố vấn học thuật yêu cầu mỗi bạn phải làm sạch dãy mã sinh viên này sao cho mọi mã còn lại đều khác nhau (không có mã nào trùng lặp). Tuy nhiên, do hạn chế giao diện phần mềm, mỗi thao tác chỉ có thể là:

• Xóa mã đầu tiên trong danh sách.
• Xóa mã cuối cùng trong danh sách.

Nhiệm vụ của bạn là xác định số thao tác ít nhất cần thực hiện để danh sách chỉ còn các mã phân biệt.

Input

Dòng đầu tiên là một số nguyên ~n~ (~1 \leq n \leq 10^5~) — số lượng mã sinh viên được ghi nhận.

Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~1 \leq a_i \leq 10^5~) — danh sách mã sinh viên.

Output

In ra một số nguyên duy nhất — số thao tác tối thiểu cần thực hiện để danh sách trở nên phân biệt.

Sample input 1

4
4 3 3 2

Sample output 1

2

Sample input 2

5
1 2 3 4 5

Sample output 2

0

Giải thích

Trong Ví dụ trên, có thể xóa 2 phần tử đầu tiên để được ~[3, 2]~, hoặc 2 phần tử cuối cùng để được ~[4, 3]~. Cả hai đều là dãy gồm các phần tử phân biệt, và cần đúng 2 thao tác.

Subtasks

• Subtask 1 (50% số điểm): ~n \le 5000~.
• Subtask 2 (50% số điểm): Không giới hạn gì thêm.