Hôm nay là 1 ngày đẹp trời, Kluco vừa học xong cách đếm số, cô giáo hpgiakhang1405 đã cho Kluco 1 bài tập đếm số như sau:

Cô giáo cho Kluco ~n~ số tự nhiên và ~q~ câu hỏi. Với mỗi câu hỏi chứa 1 số tự nhiên ~q_i~, Kluco sẽ phải đếm số lượng số lượng phần tử ~q_i~ có trong ~n~ số tự nhiên đã cho.

Vì cô giáo này là ác quỷ, nên số lượng số quá nhiều khiến Kluco choáng váng, nên anh ấy đã nhờ bạn giúp anh ấy hoàn thành bài tập này.

Input

• Dòng đầu tiên số nguyên ~n~ ~(1 \leq n \leq 2 \times 10^5)~.
• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_i~ ~(-10^9 \leq a_i \leq 10^9)~.
• Dòng tiếp theo chứa số nguyên ~q~ ~(1 \leq q \leq 2 \times 10^5)~.
• ~q~ dòng tiếp theo chứa các số ~q_i~ ~(-10^9 \leq q_i \leq 10^9)~.

Output

• ~q~ dòng là số lượng số ~q_i~ có trong ~n~ số tự nhiên đã cho.

Sample Input

3
1 1 2
3
1
2
3

Sample Output

2
1
0

Ba người chơi một trò chơi như sau: mỗi người viết ra ~n~ từ khác nhau, mỗi từ có độ dài ~3~ ký tự. Sau đó, họ tính tổng điểm theo quy tắc sau:

• Nếu một từ chỉ được viết bởi một người ~-~ người đó nhận được 3 điểm.
• Nếu một từ được viết bởi hai người ~-~ mỗi người trong hai người đó nhận 1 điểm.
• Nếu một từ được viết bởi cả ba người ~-~ không ai nhận được điểm nào.

Kết thúc trò chơi, hỏi tổng điểm của ba người là bao nhiêu (số điểm ban đầu của cả ba đều bằng ~0~)?

Input

• Dòng đầu tiên số nguyên ~n~ ~(1 \leq n \leq 10^4)~ ~-~ số lượng từ được viết ra bởi mỗi người.
• Ba dòng tiếp theo, mỗi dòng chứa ~n~ từ khác nhau ~-~ các từ được viết bởi mỗi người. Mỗi từ bao gồm ~3~ ký tự tiếng Anh viết thường.

Output

Một dòng gồm ba số nguyên là số điểm của ba người chơi (theo thứ tự người chơi tăng dần).

Sample Input 1

1
abc
def
abc

Sample Output 1

1 3 1

Sample Input 2

3
orz for qaq
qaq orz for
cod for ces

Sample Output 2

2 2 6

Sample Input 3

5
iat roc hem ica lly
bac ter iol ogi sts
bac roc lly iol iat

Sample Output 3

9 11 5

Một từ hoặc câu được gọi là pangram nếu nó chứa tất cả các chữ cái của bảng chữ cái trong ngôn ngữ đó ít nhất một lần. Pangram thường được sử dụng để thử nghiệm kiểu chữ trong in ấn và thiết bị đầu ra.

Bạn có một chuỗi gồm các chữ cái Latin viết hoa và viết thường. Hãy kiểm tra xem chuỗi này có phải là pangram hay không. Một chữ cái được coi là có mặt trong chuỗi nếu nó xuất hiện dưới dạng viết hoa hoặc viết thường.

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 100)~ - độ dài của chuỗi cần kiểm tra.
• Dòng thứ hai bao gồm một chuỗi chứa các chữ cái Latin viết hoa và viết thường.

* Output *

• In YES nếu chuỗi là pangram, ngược lại in NO.

Sample Input 1

26
MGJYIZDKsbhpVeNFlquRTcWoAx

Sample Output 1

YES

Giới thiệu: Đây là đề Training Python 3

Nam hay sử dụng mạng xã hội để giết thời gian. Trong trang danh sách trò chuyện, khi Nam gửi tin nhắn đến một người bạn nào đó, thì cuộc trò chuyện của người bạn đó sẽ xuất hiện ở đầu trang. Thứ tự đối với các cuộc trò chuyện khác không thay đổi. Trong trường hợp nếu không có cuộc trò chuyện nào với người bạn này trước đó, thì cuộc trò chuyện mới sẽ được chèn vào đầu danh sách trò chuyện.

Giả sử rằng Nam chưa có cuộc trò chuyện nào trước đó, và Nam tạo một danh sách các cuộc trò chuyện sau khi tất cả các tin nhắn của anh ấy đã được gửi đi thành công. Giả sử không có người bạn nào nhắn bất kì tin nhắn nào cho Nam.

Input

Dòng đầu tiên chứa 1 số ~n~ ~(1 \le n \le 200 000)~ - số tin nhắn mà Nam gửi.

~n~ dòng tiếp theo hiển thị người nhận tin nhắn được sắp xếp theo thứ tự tin nhắn được gửi. Tên của mỗi người tham gia cuộc trò chuyện là một dãy kí tự gồm các chữ cái tiếng Anh viết thường có độ dài tối đa là ~10~ kí tự.

Output

In tất cả những người mà Nam đã nói chuyện theo thứ tự các cuộc trò chuyện từ trên xuống dưới.

Examples 1

Input

4
alex
ivan
roman
ivan

Output

ivan
roman
alex

Examples 2

Input

8
alina
maria
ekaterina
darya
darya
ekaterina
maria
alina

Output

alina
maria
ekaterina
darya

Note

Trong test case 1, Nam gửi tin nhắn cho bạn có tên "alex", danh sách chat của Nam sẽ hiển thị như sau:

1. alex

Sau đó Nam gửi tin nhắn cho bạn "ivan", danh sách chat của Nam sẽ hiển thị như sau:

1. ivan
2. alex

Nam gửi tin nhắn thứ 3 cho người bạn tên "roman", danh sách trò chuyện của Nam sẽ được hiển thị như sau:

1. roman
2. ivan
3. alex

Nam viết tin nhắn thứ tư cho bạn bè bằng tên "ivan", cho người mà anh ta đã gửi tin nhắn, vì vậy danh sách các cuộc trò chuyện thay đổi như sau:

1. ivan
2. roman
3. alex

Trong giờ học lập trình, thầy giáo Nghialaptrinh giao cho lớp một bài tập về dấu ngoặc. ctanh2610dona thì rất nghiêm túc, còn Godsent thì nghịch ngợm, suốt ngày ghép dấu ngoặc lung tung. Một hôm, ctanh2610dona viết lên bảng một chuỗi toàn dấu ngoặc ( và ), rồi hỏi Godsent: "Ê Bảo, chuỗi này có hợp lệ không?". Anh ấy nghe xong nhưng không hiểu, liền quay sang cầu cứu bạn. Bạn hãy giúp anh ấy nhé!

Biết rằng chuỗi ngoặc hợp lệ nghĩa là:

1. Mỗi dấu ngoặc mở ( đều phải có một dấu ngoặc đóng ) đi kèm.
2. Không được có ngoặc đóng ) xuất hiện trước ngoặc mở (.

Input

• Một chuỗi chỉ gồm các ký tự ( và ), độ dài ≤ 10^5.

Output

• In ra "YES" nếu chuỗi hợp lệ.
• In ra "NO" nếu chuỗi không hợp lệ.

Ví dụ

Input 1

(()())

Output 1

YES

Input 1

())(

Output 1

NO

Trong một xưởng làm bánh, ông chủ Godsent giao cho Nghialaptrinh một dãy n nguyên liệu, được đánh số từ 1 đến n.
Mỗi nguyên liệu a[i] thuộc về một loại bánh nhất định.

Ông chủ có k thùng chứa, được đánh số từ 1 đến k.

Ông chủ Godsent muốn Nghialaptrinh kiểm tra các phân đoạn nguyên liệu trên dây chuyền để làm ra những "gói bánh tuyệt vời".

Những gói bánh được tạo ra từ một phân đoạn nguyên liệu [l, r] sẽ được gọi là tuyệt vời nếu:

• Tất cả nguyên liệu trong đoạn con [l, r] được đưa vào thùng số 1.
• Tất cả các nguyên liệu còn lại (nằm ngoài đoạn con) có thể được phân chia tùy ý vào bất kỳ trong k thùng (bao gồm cả thùng số 1).
• Sau khi phân chia xong, cả k thùng đều chứa chính xác cùng một số lượng nguyên liệu của mỗi loại bánh.

Do quá kém trong việc lập trình, nên bạn hãy giúp Nghialaptrinh: Đếm số lượng đoạn con tuyệt vời nhé.

Input

• Dòng đầu tiên chứa số nguyên t (1 ≤ t ≤ 1000) - số lượng test case
• Dòng đầu tiên của mỗi test case chứa hai số nguyên n và k (1 ≤ n ≤ 2 * 10^5, 1 ≤ k ≤ n) — số lượng nguyên liệu và số lượng thùng.
• Dòng thứ hai chứa n số nguyên a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ n) — Các loại nguyên liệu.

• Tổng tất cả các test case không vượt quá 2*10^5

  Output

• In ra một số nguyên duy nhất — số lượng đoạn con tuyệt vời.

Example

Input

4
3 2
1 1 1
4 2
1 2 1 2
8 2
3 3 3 3 2 2 2 2
6 3
1 1 1 1 1 1

Output

0
7
18
11

Giải thích test case:

test case 2: n = 4, a = [1, 2, 1, 2], k = 2

Tổng cộng có 2 nguyên liệu loại 1 và 2 nguyên liệu loại 2.

Muốn chia đều cho 2 thùng thì mỗi thùng phải có 1 nguyên liệu loại 1 và 1 nguyên liệu loại 2.

a[1->1] -> Thùng 1 chứa [1] -> còn lại [2,1,2]. Ta phân chia cho [2] vào thùng 1 -> [1,2] và đưa [1,2] còn lại vào thùng 2 -> [1,2]

-> Thùng 1 [1,2] = Thùng 2 [1,2] -> 1

a[2->2] -> Thùng 1 [2,1] = Thùng 2 [1,2] -> 2

a[3->3] -> Thùng 1 [1,2] = Thùng 2 [1,2] -> 3

a[4->4] -> Thùng 1 [2,1] = Thùng 2 [1,2] -> 4

a[1->2] -> Thùng 1 [1,2] = Thùng 2 [1,2] -> 5

a[2->3] -> Thùng 1 [2,1] = Thùng 2 [1,2] -> 6

a[3->4] -> Thùng 1 [1,2] = Thùng 2 [1,2] -> 7 -> answer

a[1->3] -> Thùng 1 [1,2,1] ≠ Thùng 2 [2]

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.

Cho một chuỗi có độ dài là ~n~ có thể đã bị mã hóa theo thuật toán sau:

• Lặp qua các ước của ~n~ theo thứ tự giảm dần (tức là từ ~n~ đến ~1~).
• Với mỗi ước số ~d~, đảo ngược đoạn con ~s[1..d]~ (tức là đoạn con bắt đầu từ vị trí 1 và kết thúc tại ~d~).

Ví dụ, thuật toán trên được áp dụng cho chuỗi ~s = iuhcoder~ dẫn đến các thay đổi sau:

• iuhcoder → redochui → oderchui → doerchui.

Bạn được cho một chuỗi ~t~ đã được mã hóa (độ dài của chuỗi không vượt quá ~100~). Nhiệm vụ của bạn là giải mã chuỗi này, tức là tìm một chuỗi ~s~ sao cho thuật toán trên cho ra chuỗi ~t~. Có thể chứng minh chuỗi ~s~ này luôn tồn tại và là duy nhất.

Input

• Dòng đầu tiên của đầu vào chứa chuỗi ~t~ chỉ bao gồm các chữ cái Latin viết thường.

* Output *

• In ra chuỗi một ~s~ là yêu cầu của đề bài.

Sample Input 1

doerchui

Sample Output 1

iuhcoder

Sample Input2

uvila

Sample Output2

alivu

Sau một ngày dài làm việc mệt mỏi , Tuấn đã tắt điện thoại và đi ngủ. Nhưng lúc này, lại có một số người nhắn tin cho Tuấn.

Bạn hãy in ra thứ tự lần lượt từ đầu đến cuối tên các người nhắn tin cho Tuấn theo màn hình ứng dụng Messenger.

Input

Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 10^5)~ là số lượng người nhắn tin cho Tuấn.

~n~ dòng tiếp theo chứa tên người nhắn tin cho Tuấn.

Đảm bảo tên mỗi người có độ dài không quá 10 kí tự và theo thứ tự thời gian tăng dần. Và đảm bảo rằng ứng dụng Messenger của Tuấn lúc đi ngủ hoàn toàn trống.

Output

Dòng đầu tiên in số nguyên ~m~ là số lượng người đã nhắn tin cho Tuấn.

~m~ dòng tiếp theo in ra tên người đã nhắn tin cho Tuấn theo thứ tự như màn hình ứng dụng Messenger.

Simple Input

8
AN
BINH
LY
AN
NHI
TINH
NHI
LY

Simple Output

5
LY
NHI
TINH
AN
BINH

Đi rừng là một hoạt động được tổ chức thường xuyên trong câu lạc bộ để giúp các thành viên thư giãn sau những giờ phút miệt mài với bàn phím và dòng code. Nhưng hôm nay, không chỉ là một buổi đi rừng thông thường, mà là một cuộc thi kỹ năng sinh tồn được tổ chức ngay giữa khu rừng!

Có ~n~ thành viên tham gia cuộc thi. Thành viên thứ ~i~ được đánh giá kỹ năng thông qua chỉ số ~a_i~. Ban tổ chức quyết định chia các thành viên thành các nhóm liên tiếp, mỗi nhóm phải cạnh tranh dựa trên kỹ năng yếu nhất của nhóm mình. Cụ thể, kỹ năng của một nhóm được tính bằng giá trị nhỏ nhất trong chỉ số kỹ năng của các thành viên trong nhóm.

Để tăng độ kịch tính, mỗi đội trưởng phải báo cáo cho ban tổ chức rằng, với mỗi kích thước nhóm ~x~ (số thành viên trong nhóm là ~x~), nhóm mạnh nhất có thể đạt được kỹ năng cao nhất là bao nhiêu.

AliVu, người đứng đầu ban tổ chức, rất tò mò về kết quả này và muốn biết kỹ năng tối đa của nhóm mạnh nhất cho mỗi kích thước nhóm ~x~ ~(1 \le x \le n)~.

Input

• Dòng đầu tiên gồm một số nguyên ~n~ ~(1 \le n \le 2\times10^5)~ - số lượng thành viên tham gia.
• Dòng thứ hai là ~n~ số nguyên ~a_1, a_2,..., a_n~ ~(1 \le a_i \le 10^9~ - chỉ số kỹ năng của từng thành viên.

Output

• In ra ~n~ số nguyên trên một dòng. Với mỗi ~x~ ~(1 \le x \le n)~, in ra kỹ năng tối đa của nhóm mạnh nhất có kích thước là ~x~.

Sample Input 1

10  
1 2 3 4 5 4 3 2 1 6

Sample Output 1

6 4 4 3 3 2 2 1 1 1