Cho dãy A được sắp xếp tăng dần ~A_1,A_2,A_3,...,A_N~. Có Q truy vấn, mỗi truy vấn là một số nguyên k:

Với mỗi k, hãy in ra vị trí số đầu tiên bé nhất có giá trị lớn hơn ~k~ gọi là ~P~. Ví dụ: Dãy ~A={1,2,2,3,4,4,4,5,6,6}~; với ~k=2~→ số đầu tiên nhỏ nhất có giá trị lớn hơn k tại vị trí ~vt=4~;

Mô tả đầu vào

• Dòng đầu ghi 2 số ~N,Q~(~1 ≤ N,Q ≤ 5.10^5~)
• Dòng thứ hai ghi ~N~ số nguyên ~A_1,A_2,A_3,...,A_N~ (~∣Ai ∣ ≤ 10^ 9~ )
• Q dòng tiếp theo mỗi dòng ghi một số nguyên x.

Mô tả đầu ra

• Với mỗi truy vấn, hãy in kết quả trên một dòng là số ~P~, nếu không tồn tại giá trị lớn hơn ~k~, in ra -1.

Ví dụ:

Input

7 5
2 2 3 4 5 6 8
4
7
9
3
4

Output

5
7
-1
4
5

Cho dãy A được sắp xếp tăng dần ~A_1,A_2,A_3,...,A_N~. Có Q truy vấn, mỗi truy vấn là một số nguyên k:

Với mỗi k, hãy in ra vị trí số đầu tiên bé nhất có giá trị lớn hơn hoặc bằng ~k~ gọi là ~P~. Ví dụ: Dãy ~A={1,2,2,3,4,4,4,5,6,6}~; với ~k=2~→ số đầu tiên nhỏ nhất có giá trị lớn hơn hoặc bằng tại vị trí ~vt=2~;

Mô tả đầu vào

• Dòng đầu ghi 2 số ~N,Q~(~1 ≤ N,Q ≤ 5.10^5~)
• Dòng thứ hai ghi ~N~ số nguyên ~A_1,A_2,A_3,...,A_N~ (~∣Ai ∣ ≤ 10^ 9~ )
• Q dòng tiếp theo mỗi dòng ghi một số nguyên x.

Mô tả đầu ra

• Với mỗi truy vấn, hãy in kết quả trên một dòng là số ~P~, nếu không tồn tại giá trị lớn hơn hoặc bằng ~k~, in ra -1.

Ví dụ:

Input

7 5
2 2 3 4 5 6 8
4
7
9
3
4

Output

4
7
-1
3
4

Hành tinh Hough xa xôi được chia thành hai nửa bán cầu có trình độ khoa học kỹ thuật khác hẳn nhau. Ở Hough A, ngành khoa học máy tính và tự động hóa phát triển mạnh mẽ, mọi công việc của họ đều được thực hiện một cách tự động. Trái ngược với Hough A, ở Hough B trình độ của họ vẫn đang ở mức thời kỳ đồ sắt bởi lẽ họ đề cao lao động chân tay.

Mặc dù trình độ khoa học kỹ thuật ở hai bán cầu rất khác nhau nhưng họ vẫn chung sống hòa bình với nhau từ thế kỷ này qua thế kỷ khác. Hằng năm họ còn tổ chức một cuộc thi lớn dành cho tất cả người dân trên hành tinh. Ở Hough A có ~𝑛~ người tham dự còn Hough B có ~𝑚~ người tham dự. Nhờ chương trình đo sức khỏe nên Hough A biết trước được chỉ số sức khỏe của tất cả người dân trên hành tinh. Trong cuộc thi, mỗi lượt sẽ có hai người ở hai bán cầu lên thi đấu, người có chỉ số sức khỏe tốt hơn sẽ dành chiến thắng, mỗi người chỉ được thi đấu tối đa một lần.

Yêu cầu: Hãy cho biết mỗi người tham dự Hough B có chỉ số sức khỏe lớn hơn bao nhiêu người tham dự của Hough A

Dữ liệu vào:

• Dòng đầu tiên ghi hai số nguyên dương ~𝑛~ và ~𝑚~.

• Dòng thứ hai ghi ~𝑛~ số nguyên dương ~𝑎_1,𝑎_2,…,𝑎_𝑛~ cho biết chỉ số sức khỏe của ~𝑛~ người tham dự cuộc thi ở Hough A.

• Dòng thứ ba ghi ~𝑚~ số nguyên dương ~𝑏_1 ,𝑏_2,…,𝑏_𝑚~ cho biết chỉ số sức khỏe của ~𝑚~ người tham dự cuộc thi ở Hough B.

Kết qủa:

• Gồm 𝑚 dòng, dòng thứ ~𝑖~ cho biết người thứ ~𝑖~ ở Hough B có chỉ số sức khỏe lớn hơn bao nhiêu người ở Hough A.

Giới hạn:

• Trong tất cả các test các số nguyên không vượt quá ~10^9~

• Có 50% số test tương ứng với 50% số điểm có ~𝑛,𝑚 ≤ 10^3~

• 50% số test còn lại tương ứng với 50% số điểm có ~𝑛,𝑚 ≤ 10^5~

Ví dụ:

Input

3 4
1 4 3
4 5 3 3

Output

2 
3 
1 
1

Bạn có 2 mảng số nguyên không âm được sắp xếp theo thứ tự không giảm, mảng ~a~ gồm ~n~ phần tử và mảng ~b~ gồm ~m~ phần tử.

Mảng ~c~ gồm ~m~ phần tử được xác định như sau:

~c_i~ = số lượng phần tử trong mảng ~a~ có giá trị nhỏ hơn ~b_i~

Yêu cầu: Hãy xác định mảng ~c~

Input

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

Output

1 1 2 3 4 6 6

Constrains:

• ~1 \le n,m \le 10^5~
• ~0 \le a_i, b_i \le 10^9~

Cho dãy số nguyên dương gồm N phần tử ~A_1, A_2,….A_N~. Với mỗi chỉ số ~1 \le i \le N~ đếm xem có bao nhiêu phần tử bé hơn ~A_i~.

Input:

Được chọ bởi tệp LESSTHAN.INP có cấu trúc:

• Dòng đầu tiên gồm số nguyên dương N (~2 \le N \le 10^5~)

• Dòng thứ hai gồm N số nguyên dương ~A_1, A_2,….A_N. A_i \le 10^9~

Output:

Được chọ bởi tệp LESSTHAN.OUT có cấu trúc:

• In ra N số nguyên, số thứ i cho biết số phần tử nhỏ hơn Ai.

Example:

Input:

5
3 2 1 1 2 

Output:

4 2 0 0 2

Constraints:

• Subtask 1 (50% số điểm): ~N \le 10^3~.

• Subtask 2 (50% số điểm): không ràng buộc gì thêm.

Khi nghe tin Đồng Hới có ca dịch Covid mới, thanhan liền chạy tới tiệm thuốc mua khẩu trang.

Cửa hàng có n hộp khẩu trang. Giá của mỗi hộp khẩu trang được biểu diễn bằng mảng ~A~. Hộp thứ i có giá ~A_i~ đồng.

Bất chợt có một người đàn ông tên là dinhlâm vừa thức dậy sau một giấc ngủ dài quên cả tương lai đến hỏi thanhan vài câu hỏi. Mỗi câu hỏi, thanhan sẽ trả lời số hộp khẩu trang có giá tiền nhỏ hơn ~Q~ đồng.

Input

• Dòng đầu tiên chứa số nguyên dương ~N (N \le 10^5)~.
• Dòng 2 chứa ~N~ số nguyên dương ~A_1,A_2,...,A_N~.
• Dòng thứ 3 chứa số nguyên dương ~T~ - là số câu hỏi (~T \le 10^5~).
• ~T~ dòng tiếp theo, mỗi dòng chứa 1 giá trị ~Q (Q \le 10^9~).

Output

• Gồm ~T~ dòng, mỗi dòng chứa câu trả lời cho mỗi câu hỏi.

  Example

Input

5
1 4 10 5 6
4
2
3
5
11

Output

1
1
2
5

Cho dãy số nguyên ~A~ gồm ~N~ phần tử được sắp xếp tăng dần. Hãy xác định giá trị x có xuất hiện trong mảng hay không ?

Input

• Dòng đầu tiên chứa số hai số nguyên dương ~N~ và ~K~ - độ dài của dãy, số câu hỏi ~(N,K \le 10^5)~.
• N số, các phần tử dãy ~A~ (~-10^9 \le A_i \le 10^9~)
• K số nguyên dương x (~-10^9 \le x \le 10^9~).

Output

• Gồm T dòng, mỗi dòng chứa câu trả lời cho mỗi câu hỏi.

Example

Input

10 10
1 61 126 217 2876 6127 39162 98126 712687 1000000000
100 6127 1 61 200 -10000 1 217 10000 1000000000 

Output

NO
YES
YES
YES
NO
NO
YES
YES
NO
YES

Xe tăng là một phương tiện có cách di chuyển rất đặc biệt. Các bánh xe của nó trải dài trên nền đất để tăng diện tích tiếp xúc, từ đó giảm áo lực lên nền, Giả sử xe tăng đang muốn đi từ ~p~ đến ~q~, ta có thể chia đoạn đất này thành ~𝑛~ đoạn nhỏ, đoạn thứ ~𝑖~ có độ cứng ~𝑎_𝑖~. Một xe tăng có chiều dài ~𝑙~, khối lượng ~𝑚~ có thể đi qua nếu tại mọi thời điểm, nó luôn đứng trên vùng đất có tổng độ cứng không nhỏ hơn ~𝑚~ (có nghĩa là mọi đoạn con liên tiếp độ dài ~𝑙~ của dãy ~𝑎~ đều phải có tổng lớn hơn hoặc bằng ~𝑚~).

Yêu cầu: Cho biết khối lượng ~𝑚~ của xe tăng, hãy tính chiều dài ~𝑙~ nhỏ nhất có thể có của nó để xe tăng đi qua được vùng đất này.

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên ~𝑚~,~𝑛~.

• Dòng tiếp theo chứa lần lượt các số ~𝑎_1,𝑎_2,…,𝑎_𝑛~.

Dữ liệu luôn đảm bảo tổng của mảng ~𝑎~ lớn hơn hoặc bằng ~𝑚~.

Dữ liệu ra

• Số nguyên dương ~𝑙~ là đáp án bài toán.

Giới hạn:

• ~1 ≤𝑛≤ 10^5~

• ~1 ≤𝑎_𝑖,𝑚 ≤ 10^9~

Kết quả:

Một số nguyên duy nhất là chiều dài ngắn nhất có thể của xe tăng.

Ví dụ:

Input

6 5

3 2 1 4 5

Output

3

Khác với Hiệp sĩ thành Tron, Hiệp sĩ Ba Lan tước đi sự quý phái và hạnh phúc khi giao đấu với nhau. Mỗi hiệp sĩ có một chỉ số sức mạnh và chiến thắng một hiệp sĩ khác khi và chỉ khi sức mạnh của anh ta lớn hơn sức mạnh của đối phương.

Tuy nhiên theo quy định của quốc vương thì mỗi hiệp sĩ được giao đấu với tất cả các hiệp sĩ khác. Ngoài ra, mỗi hiệp sĩ có một số lượng tiền. Sau khi chiến thắng đối thủ, một hiệp sĩ có thể giành được tiền thưởng là số tiền của đối thủ.

Bây giờ mỗi hiệp sĩ suy ngẫm: anh ta có thể có tối đa bao nhiêu tiền nếu giao đấu với các hiệp sĩ khác. Bạn nên trả lời câu hỏi này cho mỗi hiệp sĩ.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên ~N~ - là số hiệp sĩ (~1 \le N \le 2.10^5~).
• Dòng thứ hai chứa N số nguyên ~A_1, A_2,...,A_N~ - sức mạnh của các hiệp sĩ (~1 \le A_i \le 10^9~).
• Dòng thứ ba chứa N số nguyên ~B_1, B_2,...,B_N~ - số lượng tiền mỗi hiệp sĩ có(~1 \le B_i \le 10^9~).

• Dữ liệu ra:

• In ra N số nguyên - số tiền tối đa mà mỗi hiệp sĩ có thể có nếu anh ta giao đấu với tối đa các hiệp sĩ khác có sức mạnh nhỏ hơn mình.

Ràng buộc:

Ví dụ:

Input

4
4 5 9 7
1 2 11 33

Output

1 3 47 36

Tết năm nay, Đồng Hới có phố đi bộ, dọc theo tuyến phố có N địa điểm vui chơi, các địa điểm được đánh số lần lượt từ 1 đến N tính từ đầu phố. Sắp tới trên tuyến phố được trang bị thêm xe điện để dưa đón du khách. Ban đầu, Ban quản lý dự kiến bố trí 2 trạm dừng tại 2 trong số n địa điểm vui chơi, đồng thời để 2 trạm này không quá gần nhau, khoảng cách giữa 2 trạm phải lớn hơn r.

Yêu cầu: Đếm số cặp điểm vui chơi trên tuyến phố mà ban quản lý có thể chọn để đặt hai trạm dừng chân sao cho khoảng cách giữa 2 trạm lớn hơn ~r~.

Input:

• Dòng 1: chứa 2 số nguyên ~N,r~
• Dòng 2: chứa ~N~ số nguyên ~a_1, a_2,…..,a_N~.
• Với ~a_i~ là khoảng cách từ điểm vui chơi thứ i đến đầu con phố, các số cách nhau bởi 1 ký tự trống.

Output:

• In ra số lượng cặp điểm mà ban quản lý có thể chọn để đặt 2 trạm dừng chân.

Example:

Input:

4 4
1 3 5 8

Output:

2
Giải thích: Có 2 phương án chọn đó là (1,4) ; (2,4)

Constraints:

~2 \le N \le 10^5; 1 \le r, a_i \le 10^9~

Cô giáo trường tiểu học X đang dạy N học sinh tập xe đạp, các học sinh được đánh số từ 1 tới N, học sinh thứ 𝑗 có trọng lượng là A𝑗. Có một xe đạp duy nhất với tải trọng là m, hai học sinh chỉ có thể cùng lên xe nếu tổng trọng lượng của hai học sinh không vượt quá m. Cô giáo tự hỏi có bao nhiêu cách chọn hai học sinh khác nhau cho cùng lên xe, sau nhiều giờ tính toán không có kết quả, cô quyết định hỏi các chuyên gia lập trình giải bài toán trên.

Yêu cầu: Đếm số cặp chỉ số i, j trong đó i < j và ~A_i + A_j \le M~

Input:

• Dòng 1 chứa hai số nguyên dương N,M (~ N,M \le 10^6~)
• Dòng 2 chứa N số nguyên dương ~A_1, A_2,…A_N~ (~A_i \le 10^6~)

Output:

• Ghi một số nguyên duy nhất là đáp số

Example:

Input:

5 6
1 2 3 4 5

Output:

6

Constraints:

• Subtask #1 (60% số điểm): ~n \le 10^4~.

• Subtask #2 (20% số điểm): ~n \le 10^5~.

• Subtask #3 (20% số điểm): ~n \le 10^6~.

Cho tập hợp gồm N quân bài, mỗi quân bài chứa 1 số nguyên dương, bạn cần phải chọn ra 3 quân bài sao cho tổng 3 quân bài không vượt quá M.

Input:

• Dòng đầu tiên gồm 2 số nguyên dương N, M (~2 \le N \le 10^3 ; M \le 5.10^5~)

• Dòng thứ hai gồm N số nguyên dương ~A_1, A_2,….A_N (Ai \le 10^9)~

Output:

• In ra tổng 3 quân bài gần M nhất không vượt quá M.

Example:

Input:

5 21
5 6 7 8 9

Output:

21

Có N cây gỗ, có chiều cao lần lượt là ~A_1,A_2,...,A_N~. Bạn cần lấy một lượng gỗ độ cao tối thiểu là M bằng cách chặt từ N cây theo cách như sau: chặt tất cả những phần thừa của các cây có độ cao lớn hơn H.

Yêu cầu: Hãy tìm giá trị H lớn nhất để bạn có thể lấy được lượng gỗ tối thiểu là M.

Input:

• Dòng 1 chứa 2 số nguyên N và M .
• Dòng 2 chứa N số nguyên ~A_1,A_2,...,A_N~, là chiều cao mỗi cây gỗ tương ứng. Giả sử luôn tồn tại cách chặt.

Output:

• Số H duy nhất là kết quả bài toán trên.

Example:

Input:

4 7
20 15 10 17

Output:

15
Giải thích:  
Cây 1 chặt được (20-15)=5.
Cây 4 chặt được (17-15)=2.
Tổng số gỗ chặt được nếu H=15 là 7.

Constraints:

~1 \le N \le 2.10^5 ; 1 <= M <= 2.10^6 ; A_i \le 10^5~

Tại sân bay Đồng Hới, một đoàn khách gồm M người chuẩn bị tham gia chuyến bay. Vì số lượng khách quá lớn nên điểm kiểm soát của sân bay đã được tăng lên thành N điểm. Tại điểm kiểm soát thứ i, cần mất ~A_i~ (s) để có thể kiểm tra xong một người (tính cả thời gian đi bộ từ địa điểm xếp hàng tới điểm kiểm tra này). Các hành khách sắp xếp theo một hàng đợi. Lần lượt từng người vào một. Hành khách ở đầu hàng đợi được phép đi vào một trạm kiểm soát nào đó nếu như trạm kiểm soát đó đang trống. Tuy nhiên, người đó cũng có quyền đứng chờ để đợi một trạm kiểm soát khác trống để đi tới trạm đó, vì có thể giảm thiểu chi phí thời gian cho cả đoàn.

Yêu cầu: Các bạn hãy tính toán xem thời gian nhỏ nhất có thể để đoàn hành khách kiểm tra xong hành lý là bao nhiêu?

Input:

• Dòng đầu tiên gồm 2 số nguyên N và M, lần lượt là số quầy gửi đồ và số vị khách.
• Dòng 2 ghi N số nguyên ~A_1, A_2,...,A_N~ lần lượt là thời gian kiểm tra xong một người của trạm thứ i.

Output:

• In ra đáp số của bài toán.

Example:

Input:

2 6 
7 10

Output:

28

Constraints:

~1 \le A_i \le 10^9 ; N \le 10^5, M \le 10^6~

Nghệ nhân nấu ăn Sơn Mập có thể sử dụng hệ thống gồm ~n~ bếp điện để thực hiện nấu món ăn khiến ông được vinh danh, đó là món "Gatô hải sản". Thời gian để thực hiện nấu một suất ăn như vậy trên các bếp điện tương ứng là ~t_1, t_2, …, t_n~ giây.

Yêu cầu: Cho biết ~s~ là số lượng thực khách cần phục vụ, hãy xác định thời gian tối thiểu cần thiết để Nghệ nhân Sơn Mập có thể nấu xong ~s~ suất ăn trên hệ thống bếp điện của khách sạn. Để nấu mỗi suất ăn chỉ được sử dụng một bếp.

Input:

• Dòng đầu tiên chứa 2 số ~s~ và ~n~ lượng suất ăn ~s~ và số lượng bếp điện ~n~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~t_1, t_2, …, t_n~.

Output:

• In ra một số nguyên là thời gian tối thiểu tìm được tính bằng giây.

Example:

Input:

3 2
50 70                  

Output:

100

Constraints:

~0 < n \le 10^5; 0 < s < 10^6; 1 \le t_i \le \le 10^9~

Một dãy các số nguyên không âm ~A[1], A[2], …, A[N]~ được gọi là dãy tổng đối xứng nếu ta có thể tách dãy đó làm 2 dãy có tổng các giá trị bằng nhau. Nghĩa là tồn tại một số k trong đoạn [1..N] sao cho tổng ~A[1] + A[2] + ... + A[k] = A[k+1] + A[k+2] + ... + A[N]~.

Yêu cầu: Cho một dãy gồm ~N~ số nguyên không âm. Hãy tìm dãy con gồm các phần tử liên tiếp dài nhất mà cũng là dãy tổng đối xứng.

Input:

• Dòng đầu tiên chứa số nguyên N ~(2 \le N \le 5000)~.
• Dòng 2: chứa ~N~ phần tử ~A[i]~ của dãy ( ~i = 1, 2, …, N~). Các số trong dãy không âm và nhỏ hơn ~200000~

Output:

• Gồm một dòng: Ghi 1 số là độ dài lớn nhất của dãy con gồm các phần tử liên tiếp dài nhất là dãy tổng đối xứng. Nếu không có kết quả thì ghi số 0.

Example:

Input:

6 
2 10 3 2 5 1  

Output:

4

Cho dãy số A có N số nguyên. Hãy đếm số cặp ~(i,j)~ t sao cho ~A_i + A_j = 0~, với ~i < j~.

Input

• Dòng đầu tiên chứa một số nguyên dương N ~(1 \le 2.10^5)~.
• Dòng thứ hai chứa dãy số A gồm N số nguyên cách nhau bởi một ký tự khoảng trống ~|a_i \le 10^9|~.

Output

• In ra một số nguyên duy nhất, là số cặp phần tử trong dãy A mà có tổng là 0.

Example

Input

3
-2 0 2

Output

1

Input

6
-2 -1 0 0 1 2

Output

3

Cho một dãy gồm ~n~ số nguyên dương ~a_1, a_2,...,a_n~ (~ n \le 10^5, a_i \le 10^9~) và số ~k~.

Yêu cầu: Hãy in số nhỏ nhất lớn hơn ~k~ cùng chỉ số của nó, nếu có nhiều số nhỏ nhất lớn hơn thì in ra các chỉ số của nó.

Input

• Dòng đầu chứa số ~n~ và ~k~, dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2,...,a_n~.

Output

• Dòng đầu chứa số có giá trị nhỏ nhất lớn hơn ~k~, dòng thứ hai chứa các chỉ số của nó.

Example

Input:

6 35
91 32 43 43 451 54

Output:

43
3 4

Cho 2 số nguyên dương N,K và dãy gồm N số nguyên. Hãy tìm xem có bao nhiêu cặp số có chênh lệch đúng bằng K.

Input:

Được chọ bởi tệp CHENHLECH.INP có cấu trúc:

• Dòng đầu tiên gồm 2 số nguyên dương N,K ~(2 \le N \le 10^6; 0 \le k \le 10^9)~

• Dòng thứ hai gồm N số nguyên dương ~ 0 \le A_i \le 10^9~;

Output:

Được chọ bởi tệp CHENHLECH.OUT có cấu trúc:

• In ra số nguyên X là số cặp có độ chênh lệnh đúng bằng K.

Example:

Input:

6  2
1 3 2 4 9 5

Output:

3
Giải thích: có 3 cặp đó là: (1,3) (3,5) (2,4)

Constraints:

• Subtask 1 (50% số điểm): ~N \le 10^4~

• Subtask 2 (50% số điểm): không ràng buộc gì thêm.

Bờm được nhận vào làm việc cho nhà Phú Ông và nhiệm vụ chính của cậu ta là chăn trâu. Với bản tính ham chơi nên cậu ta đã quyết định đóng N cái cọc và cột các con trâu vào đó, vì vậy cậu ta thỏa thích chơi đùa mà không sợ các con trâu đi mất. N cái cọc được đặt trên một đường thẳng ở các vị trí ~x_1, x_2, …, x_n~. Phú Ông giao cho Bờm chăn thả C con trâu. Những con trâu này không thích bị buộc vào những chiếc cọc gần các con trâu khác. Chúng trở nên hung dữ khi bị buộc gần nhau, vì chúng cho rằng con trâu kia sẽ tranh giành cỏ của mình.

Để tránh việc các con trâu làm đau nhau, Bờm muốn buộc mỗi con trâu vào một cái cọc, sao cho khoảng cách nhỏ nhất giữa hai con trâu bất kì là lớn nhất có thể.

Yêu cầu: Hãy tìm giá trị lớn nhất này.

Input:

• Dòng 1: Ghi hai số nguyên dương N và C.

• Dòng 2: Ghi N chứa một số nguyên ~x_1,x_2,...,x_N~, với ~x_i~ mô tả vị trí của một cây cọc. Đương nhiên không có hai cây cọc nào cùng một vị trí.

Output:

• In ra giá trị lớn nhất của khoảng cách nhỏ nhất giữa hai con trâu bất kì.

Example:

Input:

5 3 
1 2 8 4 9 

Output:

3

Constraints:

~2 \le C \le N \le 10^5); 0 \le x_i \le 10^9~