Trong kì thi học sinh giỏi, mrtee phải chuẩn bị ~N~ máy tính cho ~N~ học sinh tham gia dự thi. ~N~ máy tính được xếp thẳng hàng nhau trên trục hoành của trục số, máy thứ ~i~ có toạ độ ~x_i~. Khoảng cách của hai máy ~i~ và ~j~ được tính là ~|x_i - x_j|~. Để đảm bảo nghiêm túc trong thi cử, thầy giáo muốn đặt một camera quan sát học sinh thẳng hàng với các máy trên sao cho tổng khoảng cách từ camera đến các máy tính là nhỏ nhất.

Yêu cầu: Hãy giúp thầy giáo xác định số vị trí đặt camera sao cho tổng khoảng cách từ camera đến các máy tính là nhỏ nhất.

Input

• Dòng đầu tiên chứ số nguyên dương ~N~ (~N \leq 10^6~).
• Dòng thứ hai gồm ~N~ số nguyên ~x_1, x_2, \ldots, x_N~ - toạ độ các máy tính (~|x_i| \leq 10^9~).

Output

• Dòng đâu tiên in ra số ~K~ - số vị trí đặt camera thoả mãn.
• Dòng thứ hai in ra các toạ độ đặt thoả mãn được sắp theo thứ tự tăng dần, cách nhau ít nhất một khoảng trắng.

Subtasks

• ~50\%~ số test ứng với ~N \leq 10^3~.
• ~50\%~ số test ứng với ~N \leq 10^5~.

Sample Test

Input:

6
3 1 7 2 5 7

Output:

3
3 4 5

Bạn được cho một mảng gồm ~n~ số nguyên dương. Ở mỗi lượt, bạn có thể chọn một phần tử và tăng hoặc giảm nó đi 1. Mục tiêu là làm cho mảng đúng thứ tự tăng dần sao cho số phép biến đổi là tối thiểu. Bạn được phép thay đổi phần tử theo bất kỳ cách nào; chúng có thể âm hoặc bằng ~0~.

Input

• Dòng đầu gồm số nguyên dương ~n~.
• Dòng sau gồm ~n~ số nguyên dương miêu tả dãy ~a~.

Output

• In ra số phép biến đổi nhỏ nhất cần thực hiện để mảng trở thành đúng thứ tự tăng dần.

Constraints .

• ~1 \le n \le 10^5~
• ~1 \le a_i \le 10^9~

Sample Input 1

7
2 1 5 11 5 9 11

Sample Output 1

9

Explanation 1

Trong ví dụ thứ nhất, mảng có thể được biến đổi như sau:

2 3 5 6 7 9 11

Trong cơn sốt tiền điện tử, bạn vô tình Long x120 một meme coin và giờ đang thành tỉ phú. Bây giờ bạn đang đau đầu không biết phải ngủ ở đâu trong căn phòng rộng lớn của mình.

Phòng của bạn được miêu tả trên một trục ~OX~, có ~n~ chiếc đèn, chiếc thứ ~i~ có công năng là ~p_i~ và độ sáng là ~c_i~ (chú ý dãy ~p~ tăng dần). Độ sáng mà chiếc đèn thứ ~i~ chiếu vào một vị trí ~x~ trên trục ~OX~ được tính bằng công thức: ~f(i,x) = max(0,c_i - |x-p_i|)~.

Giả sử bạn định ngủ tại vị trí ~x~ (với ~x~ là một số nguyên) trên trục, thì chất lượng của ánh sáng ~S(x)~ sẽ là tổng của toàn bộ ~f(i,x)~, nói cách khác bằng ~\sum_{i=1}^{n} f(i,x)~.

Bạn sẽ chỉ có thể ngủ ngon nếu tổng này lớn hơn hoặc bằng ~k~, vậy nên hãy tìm tất cả các vị trí ~x~ sao cho ~S(x) \ge k~.

Input

• Dòng đầu tiên gồm hai số nguyên ~n~ và ~k~ ~(1 \leq n \leq 2 \cdot 10^5, 1 \leq k \leq 10^{18})~.

• Dòng thứ hai gồm ~n~ số nguyên ~p_1, p_2, \dots, p_n~ ~(|p_i| \leq 10^{12}, p_1 < p_2 < \dots < p_n)~.

• Dòng thứ ba gồm ~n~ số nguyên ~c_1, c_2, \dots, c_n~ ~(1 \leq c_i \leq 10^{12})~.

Output

• In ra số vị trí ~x~ giúp bạn ngủ ngon.

Subtask

• Subtask ~1~ ~(20\%)~: ~n \le 10, |p_i|, |c_i| \le 100~
• Subtask ~2~ ~(30\%)~:~|p_i|, |c_i| \le 2 \times 10^5~
• Subtask ~3~ ~(30\%)~: ~n \le 3000~
• Subtask ~4~ ~(20\%)~: Không giới hạn gì thêm.

Example

Input 1

4 6
-5 -3 0 7
3 2 6 1

Output 1

2

Explanation 1

Tổng độ sáng tại các vị trí nguyên trong khoảng ~[-7, 7]~ như sau:

~\{1,2,4,5,6,5,5,6,5,4,3,2,1,0,1\}~.

Chỉ tại các vị trí ~-3~ và ~0~, tổng độ sáng mới đạt ít nhất ~k~.

Tại tất cả các vị trí nguyên nằm ngoài khoảng ~[-7, 7]~ đều không thỏa mãn.

Cho mảng ~a~ gồm ~n~ phần tử nguyên ~a_1,a_2,...,a_n~ và một số nguyên dương ~k~.

Hàm ~sum(l,r)~ được định nghĩa là tổng của các phần tử ~a_i~ trong đoạn con từ ~l~ tới ~r~.

Hãy chọn ra ~x~ đoạn con (~0 \le x \le k~ với ~k~ cho trước) ~[l_1,r_1], [l_2,r_2], ..., [l_x,r_x]~ thoả mãn ~1 \le l_i \le r_i \le n~ với ~\forall i \in [1,x]~ và ~r_{i-1} < l_i~ với ~\forall i \in [2,x]~ sao cho ~\sum sum(l_i,r_i) \forall i \in [1,x]~ là lớn nhất. Nói cách khác, hãy chọn ra ~x~ đoạn con không giao nhau sao cho tổng của chúng là lớn nhất.

Input: bluesky.inp

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~k~ ~(1 \le k \le n \le 3\times 10^5)~
• Dòng thứ hai gồm ~n~ số nguyên: ~a_1,a_2,...,a_n~ ~(|a_i| \le 10^9)~.

Output: bluesky.out

• In ra tổng lớn nhất tìm được.

Subtasks

• Có ~5\%~ số test ứng với ~a_i \ge 0~.
• Có ~10\%~ số test ứng với chỉ có duy nhất một vị trí mà ~a_i < 0~.
• Có ~15\%~ số test ứng với ~k = 1~.
• Có ~15\%~ số test ứng với ~1 \le k \le n \le 80~.
• Có ~15\%~ số test ứng với ~1 \le k \le n \le 300~.
• Có ~20\%~ số test ứng với ~1 \le k \le n \le 2000~.
• ~20\%~ số test còn lại không có điều kiện gì thêm.

Sample Input 1

6 1
1 -2 3 -1 5 -6

Sample Output 1

7

Sample Input 2

6 2
1 2 3 -10 5 6

Sample Output 2

17

Sample Input 3

6 4
-1 -2 -1 0 -5 -1

Sample Output 3

0

Trên trục tọa độ ~OX~ có ~n~ chuồng cừu. Chuồng thứ ~i~ ở vị trí ~x_i~ và có ~w_i~ con cừu ở đó.

Màn đêm sắp buông xuống, để tiện canh gác, bác nông dân ~ABC~ muốn dồn các con cừu vào đúng ~k~ chuồng phân biệt. Tuy nhiên, việc này cần được thực hiện sớm trước khi đêm về, vậy nên bác cần tìm cách dồn cừu sao cho mất ít thời gian nhất.

Biết thời gian để dồn các con cừu ở chuồng thứ ~i~ về chuồng thứ ~j~ là ~|x_i-x_j|\times w_i~, hãy xem nếu dồn tối ưu, thời gian ngắn nhất để các con cừu đều nằm ở trong đúng ~k~ chuồng là bao nhiêu,

Input

• Dòng đầu ghi hai số nguyên dương ~n,k~.
• ~n~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~x_i~ và ~w_i~ miêu tả tọa độ và số cừu của chuồng thứ ~i~.

Giới hạn

• ~k \le n \le 5000~.
• ~1 \le x_i \le 10^9~.
• ~1 \le w_i \le 10^6~.

Subtask

• ~20\%~ số test thỏa mãn: ~k=1~.
• ~30\%~ số test thỏa mãn: ~n \le 400~.
• ~30\%~ số test thỏa mãn: ~n \le 2000~.
• ~20\%~ số test không có ràng buộc gì thêm.

Output

In ra thời gian tối ưu để dồn các con cừu về đúng ~k~ chuồng.

Sample Input 1

6 2
10 15
12 17
16 18
18 13
30 10
32 1

Sample Output 1

182

Sample Input 2

3 1
20 1
30 1
40 1

Sample Output 2

20

Cho một dãy ~p_1,p_2,...,p_n~ là một hoán vị của ~1,2,...,n~. Bạn được thực hiện hai phép biến đổi sau:

• Chọn hai phần tử bất kì và tráo đổi,loại phép biến đổi này chỉ được thực hiện nhiều nhất một lần.
• Chọn hai phần tử kề nhau và tráo đổi, loại phép biến đổi này được thực hiện nhiều lần.

Yêu cầu: Tính số phép biến đổi ít nhất để đưa dãy hoán vị ~p_1,p_2,...,p_n~ về dãy hoán vị ~1,2,3...,n~.

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 ~p_1,p_2,...,p_n~.

Output

• In ra số bước ít nhất để đưa dãy ~p~ về hoán vị ~1,2,3,...,n~.

Constraints .

• ~1 \le N \le 10^5~.

Subtask

• Sub ~1~ ~(10\%)~: ~n = 3~.
• Sub ~2~ ~(20\%)~: ~n \le 30~.
• Sub ~3~ ~(20\%)~: ~n \le 300~.
• Sub ~4~ ~(20\%)~: ~n \le 1000~.
• Sub ~5~ ~(15\%)~: ~n \le 10^4~.
• Sub ~6~ ~(15\%)~: ~n \le 10^5~.

Sample Input 1

5
5 3 4 2 1

Sample Output 1

3