Cho mảng ~A~ gồm ~n~ phần tử ~a_1, a_2, \ldots, a_n~. Với mỗi phần tử ~i~ từ ~1~ đến ~n~, hãy tìm ~j~ sao cho ~j < i~ và ~a_j < a_i~ với ~i - j~ nhỏ nhất. Nói cách khác, với mỗi phần tử, hãy tìm phần tử gần nhất về phía bên trái nhỏ hơn nó.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ (~1 \le n \le 2 \cdot 10^5~)
• Dòng thứ gồm ~n~ số nguyên dương ~a_1, a_2, \ldots a_n~ (~1 \le a_i \le 10^9)~

Output

• Gồm một dãy ~n~ số, số ở vị trí ~i~ là vị trí phần tử gần nhất về bên trái của ~i~ mà có giá trị bé hơn ~a_i~. Nếu không tồn tại giá trị đó, in ra ~0~.

Sample Input 1

8
2 5 1 4 8 3 2 5

Sample Output 1

0 1 0 3 4 3 3 7

Gọi ~A~ là dãy số với ~A(i)~ được tạo bởi ghép ~i~ số nguyên tố đầu tiên với nhau: ~2, 23, 235, 2357, 235711, 23571113, ... ~.

Cho ~n~ và ~k~, hãy tìm cách xóa ~k~ chữ số ra khỏi số ~A(n)~ để thu được số lớn nhất có thể.

Input

• Gồm một dòng chứa hai số nguyên không âm ~n~ và ~k~ ~(1 \le n \le 50000)~, dữ liệu đảm bảo ~k~ bé hơn số chữ số của ~A(n)~.

  Output

• In ra một dòng miêu tả kết quả của bài toán.

Subtask

• ~50\%~ số test có ~n \le 50~.
• ~50\%~ số test không ràng buộc gì thêm.

Sample Input 1:

7 4

Sample Output 1:

711317

Bạn có một xâu ~A~ và cần thực hiện các bước sau để mã hóa xâu:

• ~Reverse(A)~: đảo ngược các kí tự trong xâu ~A~. Ví dụ ~Reverse("abc") = "cba"~.
• ~Shuffle(A)~: đổi chỗ các kí tự trong xâu ~A~. Ví dụ, ~Shuffle("god")~ có thể là ~"god", "dog", "dgo", ...~
• ~Merge(A,B)~: Trộn hai xâu ~A,B~ với nhau và giữ nguyên thứ tự của các kí tự trong từng xâu. Ví dụ ~Merge("abc","def")~ có thể là ~"abcdef", "adebcf", ...~

Xâu ~A~ (gồm các kí tự Latin in thường) ban đầu đã được mã hóa thành xâu ~S = Merge(Reverse(A),Shuffle(A))~.

Cho xâu ~S~, hãy xác định xâu ~A~ trước khi mã hóa. Do có thể có nhiều kết quả, hãy in ra xâu ~A~ có thứ tự từ điển nhỏ nhất.

Input

• Gồm một dòng chứa xâu ~S~.

Output

• In ra xâu ~A~ thỏa mãn.

Constraints .

• ~|S| \le 10^5~.

Subtask

• Sub ~1~ (~50\%~): ~n \le 1000~.
• Sub ~2~ (~50\%~): ~n \le 10^5~.

Sample Input 1

abbabb

Sample Output 1

abb

Cho một dãy ~a~ gồm ~n~ phần tử. Ta định nghĩa ~g(l,r) = min (a[i]) \forall (l \le i \le r)~.

Tiếp đó, ta có ~f(k) = max (g(l,r)) \forall (r - l + 1= k)~, hay ~f(k)~ là giá trị lớn nhất của các ~g(l,r)~ với mọi đoạn ~(l,r)~ có độ dài ~k~.

Hãy lập trình tính các ~f(k)~ từ ~1 -> n~.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~. ~(1 \le n \le 10^5).~
• Dòng sau gồm n số nguyên dương miêu tả dãy ~a~. ~(1 \le a[i] \le 10^6~ ~\forall (1 \le i \le n))~.

Output

• In ra một dòng gồm ~n~ số miêu tả kết quả của ~f(k)~ từ ~1 -> n~.

Sample Test

Input:

10
1 2 3 4 5 4 3 2 1 6

Output:

6 4 4 3 3 2 2 1 1 1 

Cho dãy số nguyên dương ~a[1], a[2], …, a[N]~. Xét cách chia dãy số ~a~ thành ~K~ nhóm sao cho mỗi nhóm chứa một đoạn liên tiếp các phần tử của ~a~. Gọi trọng số của một cách chia là tổng các phần tử lớn nhất của mỗi nhóm

Yêu cầu: Tìm cách chia dãy số ~a~ thành ~K~ nhóm sao cho trọng số của cách chia là nhỏ nhất

Dữ liệu

• Dòng 1: 2 số nguyên dương ~N~ và ~K~ (~K \le N~)
• Dòng 2: Gồm ~N~ số nguyên dương ~a[1], a[2], …, a[N]~

Kết quả:

• Ghi ra 1 số nguyên duy nhất là trọng số tìm được

Input 1

5 1
1 2 3 4 5   

Output 1

5

Input 2

5 2
1 2 3 4 5   

Output 2

6

Giới hạn:

• 14% số điểm: ~1\le N\le100, K\le min(N, 5)~
• 18% số điểm: ~1\le N\le20~
• 21% số điểm: ~1\le N\le100~
• 47% số điểm: ~1\le N\le100000, K\le min(N, 100).~

Người thầy quốc dân Gojo Satoru giờ đang có một niềm đam mê với tin học. Để lan tỏa điều này, anh muốn đố các học sinh của mình một bài toán như sau: Cho một dãy số nguyên ~a~ gồm ~n~ phần tử, định nghĩa ~f(l,r)~ là ~max(a_i) - min(a_i) \forall (l \le i \le r)~.

Hãy tính tổng của ~f(l,r) \forall (1 \le l \le r \le n)~.

Tất nhiên, do bận đi làm nhiệm vụ, các học sinh của thầy không rảnh để giải bài toán này, hãy thử giải nó giúp họ nhé.

Input:

• Dòng đầu gồm số nguyên dương ~n~. ~(1 \le n \le 10^5)~.
• Dòng sau gồm n số nguyên miêu tả dãy ~a~. ~(|a_i| \le 10^6)~.

Output:

• Ghi ra một số nguyên miêu tả kết quả của bài toán.

Subtasks

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

Sample Test

Input:

3
1 2 3

Output:

4

Giải thích:

Ta có ~f(1,1) + f(1,2) + f(1,3) + f(2,2) + f(2,3) + f(3,3) = 0 + 1 + 2 + 0 + 1 +0 = 4~.

Vào năm ~3202~, trò chơi "Fake Pyramid" đang vô cùng thịnh hành với giới trẻ.

Trong trò chơi này, bạn được nhận một mảnh giấy kẻ ~n~ dòng và ~m~ cột, tạo ra ~n \times m~ ô vuông. Ô ở hàng ~i~ và cột ~j~ được gọi là ô ~(i,j)~. Mỗi ô ~(i,j)~ đều có một giá trị là ~a_{i,j}~, nếu ~a_{i,j} = 0~ thì nghĩa là ô đó đã bị "cấm", ngược lại, ~a_{i,j}~ sẽ mang một giá trị nguyên dương.

Bạn cần tìm cách vẽ ra một kim tự tháp trên mảnh giấy được cho theo luật như sau (do vẽ trên giấy nên có thể sẽ khác so với tưởng tượng):

• Đầu tiên, bạn chọn ra hai giá trị ~A,B~ thỏa mãn ~1 \le A \le B \le n~.
• Với mỗi ~i~ thuộc đoạn ~[A,B]~, bạn chọn ra hai giá trị ~L_i,R_i~ thỏa mãn ~1 \le L_i \le R_i \le m~. Bạn cần chọn các giá trị ~L_i,R_i~ này sao cho với mọi ~i \in [A,B-1]~, ~L_i \ge L_{i+1}~ và ~R_i \le R_{i+1}~
• Sau khi chọn xong các giá trị, bạn sẽ thu được một kim tự tháp được tạo bởi các ô ~(i,j)~ thỏa mãn ~i \in [A,B]~ và ~j \in [L_i,R_i]~.
• Nói cách khác, với mỗi hàng từ ~A~ tới ~B~, bạn sẽ cần chọn ra một số ô liên tiếp sao cho các ô ở hàng dưới trùm lên các ô ở hàng trên.
• Để tăng độ khó cho trò chơi, kim tự tháp của bạn vẽ ra không được chứa ô nào bị cấm.
• Giá trị của một kim tự tháp chính là tổng giá trị các ô nó chứa.

Ví dụ, cho mảnh giấy ~5 \times 5~ có minh họa như sau:

Ta chọn:

• ~A = 1; B = 3~.
• ~L_1 = 1; R_1 = 1~.
• ~L_2 = 1; R_2 = 3~.
• ~L_3 = 1; R_3 = 3~.

Sẽ thu được kim tự tháp thỏa mãn ở dưới (những ô màu cam là những ô nằm trong kim tự tháp):

Dưới đây cũng là một kim tự tháp thỏa mãn:

Tuy nhiên, hình ảnh dưới đây lại không phải một kim tự tháp thỏa mãn do chứa ô có giá trị ~a(i,j) = 0~ (ô bị cấm):

Cuối cùng, ta có minh họa dưới đây cũng không phải một kim tự tháp do ~L_4 < L_5~

MoHuymed Salah rất hứng thú với trò chơi này, nhưng do anh đang bận rộn với định lý một mùa dài ~7~ năm của mình nên dù đã có một mảnh giấy nhưng chưa có thời gian để tìm ra lời giải tối ưu nhất. Bạn hãy giúp anh ấy nhé.

Yêu cầu: Cho ma trận ~n \times m~ miêu tả mảnh giấy, hãy tìm cách vẽ kim tự tháp sao cho thu được tổng lớn nhất có thể.

Dữ liệu vào từ tệp văn bản: kimtuthap.inp

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~m~ ~(1 \le n,m \le 2000)~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa ~m~ số nguyên dương ~a_{i,1}, a_{i,2}, ..., a_{i,m}~ miêu tả mảng giá trị ~a~ ~(a_{i,j} \le 50)~.
• Dữ liệu đảm bảo luôn luôn tồn tại ít nhất một giá trị ~a(i,j) \neq 0~.

Kết quả ghi ra tệp văn bản: kimtuthap.out

• In ra một số nguyên là giá trị lớn nhất có thể đạt được của một kim tự tháp.

Ràng buộc

• Có ~15\%~ số test thỏa mãn: ~n = 1~.
• Có ~20\%~ số test thỏa mãn: Nếu hàng ~i~ ~(1 \le i \le n)~ có ô bị cấm, thì tất cả các ô trong hàng đó cũng đều bị cấm.
• Có ~20\%~ số test thỏa mãn: ~n,m \le 60~.
• Có ~25\%~ số test thỏa mãn: ~n,m \le 300~.
• ~20\%~ số test còn lại không có ràng buộc gì thêm.

Ví dụ

Input 1

5 5
5 0 1 4 4
7 12 6 5 4
5 7 8 0 1
1 6 4 5 0
1 0 7 5 8

Output 1

66

Input 2

5 3
1 1 2
0 0 0
1 2 3
2 3 4
0 0 0

Output 2

15

Giải thích

Ở ví dụ ~1~, ta lấy kim tự tháp theo hình dưới đây:

Còn đây là kim tự tháp ta cần lấy ở ví dụ ~2~:

Cho một hoán vị ~p_1,p_2,…,p_n~. Bạn cần trả lời ~q~ truy vấn. Truy vấn thứ ~i~ là một cặp số nguyên (~l_i,r_i~ ), bạn cần tính ~f(l_i,r_i )~.

Gọi ~m_{l,r}~ là vị trí của phần tử lớn nhất trong đoạn ~p_l,p_{l+1},…,p_r~

~f(l,r)=(r-l+1)+f(l,m_{l,r}-1)+f(m_{l,r}+1,r)~ nếu ~l \leq r~ và bằng 0 trong trường hợp ngược lại .

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ (~1 \leq n, q \leq 10^6~) - kích thước của hoán vị ~𝑝~ và số lượng truy vấn.
• Dòng thứ hai chứa ~n~ các số nguyên đôi một phân biệt ~p_1,p_2,…,p_n~ ~(1 \leq p_i \leq n, p_i \neq p_j \forall i \neq j)~ - hoán vị ~p~.
• Dòng thứ ba chứa ~q~ số nguyên ~l_1,l_2,…,l_q~ – giá trị ~l~ của các truy vấn.
• Dòng thứ tư chứa ~q~ số nguyên ~r_1,r_2,…,r_q~ – giá trị ~r~ của các truy vấn.
• Đầu vào đảm bảo rằng ~1 \leq l_i \leq r_i \leq n~ cho tất cả các truy vấn.

Output

• In ~q~ số nguyên - các giá trị ~f(l_i,r_i )~ cho các truy vấn tương ứng.

Subtask

• Subtask ~1~ (30%): ~1 \leq n, q \leq 500~
• Subtask ~2~ (30%): ~1 \leq n, q \leq 5000~
• Subtask ~3~ (20%): Hoán vị được sắp xếp tăng dần hoặc giảm dần
• Subtask ~4~ (20%): Giới hạn gốc

Example

Sample input

4 5
3 1 4 2
2 1 1 2 3
2 4 3 4 4

Sample output

1 8 6 5 3

Đối với một dãy ~b_1,b_2,...,b_m~, một vị trí ~1 \le i < m~ được gọi là "cutable" nếu như tất cả các phần tử trong đoạn ~[b_1,b_2,...,b_i]~ đều bé hơn các phần tử trong đoạn ~[b_{i+1},...,b_m]~.

Cho dãy nguyên dương ~a_1,a_2,...,a_n~ gồm các số nguyên phân biệt trong đoạn ~[1,n]~. Bạn cần trả lời ~q~ truy vấn, mỗi truy vấn gồm hai số nguyên dương ~l,r~. Hãy đếm số vị trí "cutable" đối với dãy ~a_l,a_{l+1},...,a_r~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~.
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1,a_2,...,a_n~ miêu tả hoán vị ~a~.
• Dòng thứ ba chứa số nguyên dương ~q~.
• ~q~ dòng sau, mỗi dòng gồm hai số nguyên dương ~l,r~ ~(1 \le l < r \le n)~ miêu tả truy vấn.

Output

• Với mỗi truy vấn, in ra kết quả tương ứng.

Constraints .

• ~1 \le n,q \le 2*10^5~

Subtask

• Sub ~1~ (~50\%~): ~n,q \le 1000~.
• Sub ~2~ (~50\%~): ~n,q \le 3 \times 10^5~.

Sample Input 1

6
1 4 2 3 6 5
4
1 4
2 5
1 6
5 6

Sample Output 1

1
1
2
0

Cho một bảng vuông kích thước ~n \times n~. Mỗi ô của bảng chứa một trong hai ký tự ~0~ hoặc ~1~.

Một hình chữ nhật con của bảng được gọi là hình chữ nhật 0 nếu tất cả các ô nằm trong hình chữ nhật đó đều có giá trị ~0~.

Ban đầu, hãy tính số lượng hình chữ nhật 0 trong bảng.

Sau đó có ~q~ truy vấn. Mỗi truy vấn cho một ô ~(r, c)~, yêu cầu đảo giá trị của ô đó:

• Nếu ô đang có giá trị ~0~, đổi thành ~1~.
• Nếu ô đang có giá trị ~1~, đổi thành ~0~.

Sau mỗi truy vấn, hãy tiếp tục tính số lượng hình chữ nhật 0 trong bảng hiện tại.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~q~.
• ~n~ dòng tiếp theo, mỗi dòng gồm ~n~ ký tự ~0~ hoặc ~1~, mô tả bảng ban đầu.
• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~r~ và ~c~ mô tả truy vấn đảo giá trị ô ~(r, c)~.

Output

In ra ~q + 1~ dòng.

• Dòng đầu tiên in ra số lượng hình chữ nhật 0 trong bảng ban đầu.
• Dòng thứ ~i + 1~ in ra số lượng hình chữ nhật 0 sau khi thực hiện truy vấn thứ ~i~.

Giới hạn

• ~1 \le n, q \le 5000~
• ~1 \le r, c \le n~

Subtasks

Sample Test

Input:

3 3
000
010
000
2 2
1 1
2 2

Output:

20
36
27
15

Giải thích

Ban đầu, bảng có một ô ~1~ ở vị trí ~(2, 2)~, số lượng hình chữ nhật toàn ~0~ là ~20~.

• Sau truy vấn thứ nhất, ô ~(2, 2)~ đổi từ ~1~ thành ~0~, toàn bộ bảng đều là ~0~, có ~36~ hình chữ nhật 0.
• Sau truy vấn thứ hai, ô ~(1, 1)~ đổi từ ~0~ thành ~1~, còn ~27~ hình chữ nhật 0.
• Sau truy vấn thứ ba, ô ~(2, 2)~ đổi từ ~0~ thành ~1~, còn ~15~ hình chữ nhật 0.

Có một hàng đợi ban đầu trống. Bạn cần xử lý ~q~ truy vấn có dạng sau:

• Thêm 1 phần tử ~x~ vào cuối hàng

• Tăng giá trị các phần tử hiện tại trong hàng lên ~v~

• Xóa các phần tử có giá trị là ~x~ tại thời điểm hiện tại

Input

• Dòng đầu tiên gồm số nguyên dương ~q~ là số truy vấn (~1 \le q \le 10^5~).

• ~q~ dòng tiếp theo mỗi dòng là một truy vấn có dạng như sau:

  • ~1~ ~x~: Thêm 1 phần tử ~x~ vào cuối hàng (~1 \le x \le 10^5~).

  • ~2~ ~v~: Tăng giá trị các phần tử hiện tại trong hàng lên ~v~ (~1 \le v \le 10^5~).

  • ~3~ ~x~: Xóa các phần tử có giá trị là ~x~ tại thời điểm hiện tại (~1 \le x \le 10^5~).

Output

• Dòng đầu tiên in ra số lượng phần tử còn lại trong hàng sau ~q~ truy vấn.

• Dòng thứ hai in ra các phần tử ở trong hàng theo thứ tự từ đầu đến cuối.

Scoring

Sample Input 1

9
1 1
1 2
1 3
3 3
2 1
1 3
3 3
2 5
1 6

Sample Output 1

2
7 6

Notes

Ở test ví dụ trên:

• Sau truy vấn thứ nhất, dãy ~a = \{1\}~

• Sau truy vấn thứ hai, dãy ~a = \{1,2\}~

• Sau truy vấn thứ ba, dãy ~a = \{1,2,3\}~

• Sau truy vấn thứ tư, dãy ~a = \{1,2\}~

• Sau truy vấn thứ năm, dãy ~a = \{2,3\}~

• Sau truy vấn thứ sáu, dãy ~a = \{2,3,3\}~

• Sau truy vấn thứ bảy, dãy ~a = \{2\}~

• Sau truy vấn thứ tám, dãy ~a = \{7\}~

• Sau truy vấn cuối cùng, dãy ~a = \{7,6\}~