Một xưởng có \(n\) máy có thể được sử dụng để làm sản phẩm. Mục tiêu của bạn là tạo ra tổng cộng \(t\) sản phẩm.

Đối với mỗi máy, bạn biết số giây cần thiết để tạo ra một sản phẩm duy nhất. Các máy có thể hoạt động đồng thời, và bạn có thể tự do quyết định lịch trình của chúng.

Thời gian cần thiết ngắn nhất để tạo ra \(t\) sản phẩm là bao nhiêu?

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(t\): số lượng máy và sản phẩm.
• Dòng tiếp theo có \(n\) số nguyên \(k_1,k_2,\ldots,k_n\): thời gian cần thiết để tạo ra một sản phẩm bằng mỗi máy.

Output

• In một số nguyên: thời gian tối thiểu cần thiết để tạo ra \(t\) sản phẩm.

Constraints

• \(1 \le n \le 2 \cdot 10^5\)
• \(1 \le t \le 10^9\)
• \(1 \le a_i \le 10^9\)

Example

Sample input

3 7
3 2 5

Sample output

8

Note

Máy \(1\) làm hai sản phẩm, máy \(2\) làm bốn sản phẩm và máy \(3\) làm một sản phẩm.

Bạn được cho một mảng chứa \(n\) số nguyên dương.

Nhiệm vụ của bạn là chia mảng thành \(k\) đoạn con sao cho tổng lớn nhất trong các đoạn con nhỏ nhất có thể.

Input

• Dòng đầu vào đầu tiên chứa hai số nguyên \(n\) và \(k\): kích thước của mảng và số lượng đoạn con trong cách chia.
• Dòng tiếp theo chứa \(n\) số nguyên \(x_1,x_2,\ldots,x_n\): nội dung của mảng.

Output

• In một số nguyên: tổng lớn nhất của một đoạn con trong cách chia tối ưu.

Constraints

• \(1 \leq n \leq 2 \cdot 10 ^ 5\)
• \(1 \leq k \leq n\)
• \(1 \leq x_i \leq 10 ^ 9\)

Example

Sample input

5 3
2 4 7 3 5

Sample output

8

Note

Một cách chia tối ưu là \([2,4],[7],[3,5]\) trong đó tổng của các đoạn con là \(6,7,8\). Tổng lớn nhất là tổng cuối cùng \(8\).

Với một mảng gồm \(n\) số nguyên, nhiệm vụ của bạn là tính toán số lượng đoạn con có nhiều nhất \(k\) giá trị phân biệt.

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(k\): kích thước của mảng và số lượng giả trị phân biệt tối đa.
• Dòng tiếp theo có \(n\) số nguyên \(x_1,x_2,\ldots,x_n\): nội dung của mảng.

Output

• In một số nguyên: số lượng đoạn con.

Constraints

• \(1 \le k \le n \le 2 \cdot 10^5\)
• \(1 \le x_i \le 10^9\)

Example

Sample input

5 2
1 2 3 1 1

Sample output

10

Cho một mảng gồm \(n\) số nguyên, nhiệm vụ của bạn là đếm số lượng đoạn con trong đó tổng các giá trị chia hết cho \(n\).

Input

• Dòng đầu vào đầu tiên có một số nguyên \(n\): kích thước của mảng.
• Dòng tiếp theo có \(n\) số nguyên \(x_1,x_2,\ldots,x_n\): nội dung của mảng.

Output

• In một số nguyên: số lượng đoạn con được yêu cầu.

Constraints

• \(1 \le n \le 2 \cdot 10^5\)
• \(-10^9 \le a_i \le 10^9\)

Example

Sample input

5
3 1 2 7 4

Sample output

1

Cho một mảng gồm \(n\) số nguyên dương, nhiệm vụ của bạn là đếm số lượng đoạn con có tổng \(x\).

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(x\): kích thước của mảng và tổng \(x\).
• Dòng tiếp theo có \(n\) số nguyên \(a_1, a_2, \ldots, a_n\): nội dung của mảng.

Output

• In một số nguyên: số lượng đoạn con được yêu cầu.

Constraints

• \(1 \le n \le 2 \cdot 10^5\)
• \(1 \le x, a_i \le 10^9\)

Example

Sample input

5 7
2 4 1 2 7

Sample output

3

Cho một mảng gồm \(n\) số nguyên, nhiệm vụ của bạn là đếm số lượng đoạn con có tổng \(x\).

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(x\): kích thước của mảng và tổng \(x\).
• Dòng tiếp theo có \(n\) số nguyên \(a_1, a_2, \ldots, a_n\): nội dung của mảng.

Output

• In một số nguyên: số lượng đoạn con được yêu cầu.

Constraints

• \(1 \le n \le 2 \cdot 10^5\)
• \(-10^9 \le x, a_i \le 10^9\)

Example

Sample input

5 7
2 -1 3 5 -2

Sample output

2

Có một khách sạn lớn, và \(n\) khách hàng sẽ đến sớm. Mỗi khách hàng muốn có một phòng đơn.

Bạn biết ngày nhận phòng và trả phòng của mỗi khách hàng. Hai khách hàng có thể ở trong cùng một phòng nếu ngày trả phòng của khách hàng đầu tiên sớm hơn ngày nhận phòng của khách hàng thứ hai.

Số lượng phòng tối thiểu cần thiết để chứa tất cả khách hàng là bao nhiêu? Và các phòng có thể được phân bổ như thế nào?

Input

• Dòng đầu vào đầu tiên chứa một số nguyên n: số lượng khách hàng.
• Sau đó, có \(n\) dòng, mỗi dòng mô tả một khách hàng. Mỗi dòng có hai số nguyên \(a\) và \(b\): ngày nhận phòng và trả phòng.

Output

• In đầu tiên một số nguyên \(k\): số phòng tối thiểu cần thiết.
• Sau đó, in một dòng chứa số phòng của mỗi khách hàng theo thứ tự giống như trong đầu vào. Các phòng được đánh số \(1,2,\ldots,k\). Bạn có thể in bất kỳ giải pháp hợp lệ nào.

Constraints

• \(1 \le n \le 2 \cdot 10^5\)
• \(1 \le a \leq b \le 10^9\)

Example

Sample input

3
1 2
2 4
4 4

Sample output

2
1 2 1

Cho một mảng gồm \(n\) số nguyên, nhiệm vụ của bạn là tìm tổng giá trị tối đa của một đoạn con khác rỗng.

Input

• Dòng đầu vào đầu tiên có một số nguyên \(n\): kích thước của mảng.
• Dòng thứ hai có \(n\) số nguyên \(x_1,x_2,\ldots,x_n\): các giá trị của mảng.

Output

• In một số nguyên: tổng đoạn con lớn nhất.

Constraints

• \(1 \leq n \leq 2 \cdot 10 ^ 5\)
• \(-10 ^ 9 \leq x_i \leq 10 ^ 9\)

Example

Sample input

8
-1 3 -2 5 3 -5 2 2

Sample output

9

Có \(n\) người đăng ký và \(m\) căn hộ trống. Nhiệm vụ của bạn là phân phối các căn hộ để nhiều người có căn hộ nhất có thể.

Mỗi người đăng ký có một kích thước căn hộ mong muốn, và họ sẽ chấp nhận bất kỳ căn hộ nào có kích thước đủ gần với kích thước mong muốn.

Input

• Dòng đầu vào đầu tiên có ba số nguyên \(n\), \(m\) và \(k\): số lượng người đăng ký, số lượng căn hộ và chênh lệch tối đa cho phép.
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1,a_2,\ldots,a_n\): kích thước căn hộ mong muốn của mỗi người đăng ký. Nếu kích thước mong muốn của người đăng ký là \(x\), người đó sẽ chấp nhận bất kỳ căn hộ nào có kích thước từ \(x − k\) đến \(x + k\).
• Dòng cuối cùng chứa \(m\) số nguyên \(b_1,b_2,\ldots,b_m\): kích thước của mỗi căn hộ.

Output

• In một số nguyên: số lượng người sẽ có được một căn hộ.

Constraints

• \(1 \leq n, m \leq 2 \cdot 10^5\)
• \(0 \leq k \leq 10^9\)
• \(1 \leq a_i, b_i \leq 10^9\)

Example

Sample input

4 3 5
60 45 80 60
30 60 75

Sample output

2

Có \(n\) que với một số độ dài. Nhiệm vụ của bạn là sửa đổi các que sao cho mỗi que có cùng chiều dài.

Bạn có thể kéo dài và rút ngắn từng thanh. Cả hai thao tác đều có chi phí \(x\) trong đó \(x\) là chênh lệch giữa độ dài mới và độ dài ban đầu.

Tổng chi phí tối thiểu là bao nhiêu?

Input

• Dòng đầu vào đầu tiên chứa một số nguyên \(n\): số lượng que.
• Sau đó, có \(n\) số nguyên: \(p_1,p_2,\ldots,p_n\): độ dài của que.

Output

• In một số nguyên: tổng chi phí tối thiểu.

Constraints

• \(1 \le n \le 2 \cdot 10^5\)
• \(1 \le p_i \le 10^9\)

Example

Sample input

5
2 3 1 5 2

5

Bạn có \(n\) đồng xu với các giá trị nguyên dương. Số tiền nhỏ nhất bạn không thể tạo bằng cách sử dụng một tập hợp con của các đồng xu là bao nhiêu?

Input

• Dòng đầu vào đầu tiên có một số nguyên \(n\): số lượng đồng xu.
• Dòng thứ hai có \(n\) số nguyên \(x_1,x_2,\ldots,x_n\): giá trị của mỗi đồng xu.

Output

• In một số nguyên: tổng tiền xu nhỏ nhất.

Constraints

• \(1 \le n \le 2 \cdot 10^5\)
• \(1 \le x_i \le 10^9\)

Example

Sample input

5
2 9 1 2 7

Sample output

6

Bạn được cho một mảng mà chứa mỗi số giữa \(1\ldots n\) chính xác một lần. Nhiệm vụ của bạn là thu thập các số từ \(1\) đến \(n\) theo thứ tự tăng dần.

Trong mỗi vòng, bạn đi qua mảng từ trái sang phải và thu thập nhiều số nhất có thể. Tổng số lượng vòng sẽ là bao nhiêu?

Input

• Dòng đầu tiên có hai số nguyên \(n\): kích thước mảng.
• Dòng tiếp theo có \(n\) số nguyên \(x_1,x_2,\ldots,x_n\): các số trong mảng.

Output

• In một số nguyên: số lượng vòng.

Constraints

• \(1 \le n \le 2 \cdot 10^5\)

Example

Sample input

5
4 2 1 5 3

Sample output

3

Bạn được cho một mảng mà chứa mỗi số giữa \(1\ldots n\) chính xác một lần. Nhiệm vụ của bạn là thu thập các số từ $14 đến \(n\) theo thứ tự tăng dần.

Trong mỗi vòng, bạn đi qua mảng từ trái sang phải và thu thập nhiều số nhất có thể.

Cho \(m\) thao tác hoán đổi hai số trong mảng, nhiệm vụ của bạn là báo cáo số lượng vòng sau mỗi thao tác.

Input

• Dòng đầu tiên có hai số nguyên \(n\) và \(m\): kích thước mảng và số lượng phép toán.
• Dòng tiếp theo có \(n\) số nguyên \(x_1,x_2,\ldots,x_n\): các số trong mảng.
• Cuối cùng, có \(m\) dòng mô tả các thao tác. Mỗi dòng có hai số nguyên \(a\) và \(b\): các số tại vị trí \(a\) và \(b\) được hoán đổi.

Output

• In \(m\) số nguyên: số lượng vòng sau mỗi lần hoán đổi.

Constraints

• \(1 \le n,m \le 2 \cdot 10^5\)
• \(1 \le a,b \le n\)

Example

Sample input

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

Sample output

2
3
4

Cho biết danh sách phát của một đài phát thanh kể từ khi thành lập. Danh sách phát có tổng cộng \(n\) bài hát.

Dãy các bài hát liên tiếp dài nhất, mà mỗi bài trong đó đều độc nhất là dãy nào?

Input

• Dòng đầu vào đầu tiên chứa một số nguyên \(n\): số lượng bài hát.
• Dòng tiếp theo có \(n\) số nguyên \(k_1,k_2,\ldots,k_n\): mã số của mỗi bài hát.

Output

• In độ dài của dãy dài nhất mà mỗi bài hát là duy nhất.

Constraints

• \(1 \le n \le 2 \cdot 10^5\)
• \(1 \le k_i \le 10^9\)

Example

Sample input

8
1 2 1 3 2 7 4 2

Sample output

5

Bạn được cho \(n\) khối lập phương theo một thứ tự nhất định, và nhiệm vụ của bạn là xây dựng các tòa tháp bằng cách sử dụng chúng. Bất cứ khi nào hai khối lập phương nằm chồng lên nhau, khối lập phương phía trên phải nhỏ hơn khối lập phương dưới.

Bạn phải xử lý các khối lập phương theo thứ tự được cho. Bạn luôn có thể đặt khối lập phương lên trên đỉnh của một tòa tháp hiện có hoặc bắt đầu một tòa tháp mới. Số lượng tòa tháp tối thiểu có thể là bao nhiêu?

Input

• Dòng đầu vào đầu tiên chứa một số nguyên \(n\): số lượng khối lập phương.
• Dòng tiếp theo chứa \(n\) số nguyên \(k_1,k_2,\ldots,k_n\): kích thước của các khối lập phương.

Output

• In một số nguyên: số lượng tòa tháp tối thiểu.

Constraints

• \(1 \le n \le 2 \cdot 10^5\)
• \(1 \le k_i \le 10^9\)

Example

Sample input

5
3 8 2 1 5

Sample output

2

Có một con đường chiều dài \(x\) mà các vị trí của nó được đánh số \(0,1,\ldots,x\). Ban đầu không có đèn giao thông, nhưng \(n\) bộ đèn giao thông lần lượt được thêm vào con đường.

Nhiệm vụ của bạn là tính toán chiều dài của đoạn đường dài nhất mà không có đèn giao thông sau mỗi lần thêm.

Input

• Dòng đầu vào đầu tiên chứa hai số nguyên \(x\) và \(n\): chiều dài của đường phố và số lượng bộ đèn giao thông.
• Sau đó, dòng tiếp theo chứa \(n\) số nguyên \(p_1,p_2,\ldots,p_n\): vị trí của mỗi bộ đèn giao thông. Mỗi vị trí là phân biệt.

Output

• In chiều dài của đoạn đường dài nhất mà không có đèn giao thông sau mỗi lần thêm.

Constraints

• \(1 \le x \le 10^9\)
• \(1 \le n \le 2 \cdot 10^5\)
• \(0 < p_i < x\)

Example

Sample input

8 3
3 6 2

Sample output

5 3 3

Bạn được cho một mảng gồm \(n\) số nguyên và nhiệm vụ của bạn là tìm hai giá trị (tại các vị trí phân biệt) có tổng là \(x\).

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(x\): kích thước mảng và tổng mong muốn.
• Dòng thứ hai có \(n\) số nguyên \(a_1,a_2,\ldots,a_n\): các giá trị của mảng.

Output

• In hai số nguyên: vị trí của các giá trị. Nếu có một số lời giải, bạn có thể in bất kỳ lời giải nào trong số đó. Nếu không có lời giải nào, in IMPOSSIBLE.

Constraints

• \(1 \leq n \leq 2 \cdot 10 ^ 5\)
• \(1 \leq x, a_i \leq 10 ^ 9\)

Example

Sample input

4 8
2 7 5 1

Sample output

2 4

Có \(N\) đứa trẻ muốn đi chơi vòng đu quay, và nhiệm vụ của bạn là tìm cáp treo cho mỗi đứa trẻ.

Một cáp treo có thể chứa được \(1\) hoặc \(2\) đứa trẻ, trong đó, tổng trọng lượng mỗi cáp treo không được vượt quá \(x\). Bạn biết trọng lượng của mỗi đứa trẻ.

Hỏi số cáp treo ít nhất cần để chở hết tất cả đứa trẻ là bao nhiêu?

Input

• Dòng đầu tiên chứa \(2\) số tự nhiên \(N\) và \(x\) - Số lượng đứa trẻ và tổng trọng lượng tối đa cho phép.
• Dòng tiếp theo chứa \(N\) số tự nhiên \(p_1, p_2, p_3, \ldots ,p_N\) - trọng lượng của mỗi đứa trẻ.

Output

• In ra số lượng cáp treo tối thiểu.

Constraints

• \(1 \leq N \leq 2 * 10^5\).
• \(1 \leq p_i \leq x \leq 10^9\).

Sample Test

Input:

4 10
7 2 3 9

Output:

3

Trong một lễ hội phim, \(n\) bộ phim sẽ được chiếu. Bạn biết thời gian bắt đầu và kết thúc của mỗi bộ phim. Số lượng phim tối đa bạn có thể xem trọn vẹn là bao nhiêu?

Input

• Dòng đầu vào đầu tiên có một số nguyên \(n\): số lượng bộ phim.
• Sau này, có \(n\) dòng mô tả các bộ phim. Mỗi dòng có hai số nguyên \(a\) và \(b\): thời gian bắt đầu và kết thúc của một bộ phim.

Output

• In một số nguyên: số lượng phim tối đa.

Constraints

• \(1 \leq n \leq 2 \cdot 10^5\)
• \(1 \leq a < b \leq 10^9\)

Example

Sample input

3
3 5
4 9
5 8

Sample output

2

Bạn được cho một danh sách gồm \(n\) số nguyên và nhiệm vụ của bạn là tính toán số lượng giá trị phân biệt trong danh sách.

Input

• Dòng đầu vào đầu tiên có một số nguyên \(n\): số lượng giá trị.
• Dòng thứ hai có \(n\) số nguyên \(x_1,x_2,\ldots,x_n\).

Output

• In một số nguyên: số lượng giá trị phân biệt.

Constraints

• \(1 \le n \le 2 \cdot 10^5\)
• \(1 \le x_i \le 10^9\)

Example

Sample input

5
2 3 2 2 3

2

Có \(n\) vé hòa nhạc có sẵn, mỗi vé có một mức giá nhất định. Sau đó, \(m\) khách hàng đến, lần lượt đến.

Mỗi khách hàng thông báo mức giá tối đa mà họ sẵn sàng trả cho một vé, và sau đó, họ sẽ nhận được một vé với giá lớn nhất có thể sao cho nó không vượt quá giá tối đa.

Input

• Dòng đầu vào đầu tiên chứa các số nguyên \(n\) và \(m\): số lượng vé và khách hàng.
• Dòng tiếp theo chứa \(n\) số nguyên \(h_1,h_2,\ldots,h_n\): mức giá của mỗi vé.
• Dòng cuối cùng chứa \(m\) số nguyên \(t_1,t_2,\ldots,t_m\): mức giá tối đa của mỗi khách hàng theo thứ tự họ đến.

Output

• In, đối với mỗi khách hàng, mức giá mà họ sẽ trả cho vé của họ. Sau này, vé không thể được mua lại.
• Nếu khách hàng không thể nhận được bất kỳ vé nào, hãy in \(−1\).

Constraints

• \(1 \le n,m \le 2 \cdot 10^5\)
• \(1 \le h_i,t_i \le 10^9\)

Example

Sample input

5 3
5 3 7 8 5
4 8 3

Sample ouput

3
8
-1

Bạn được cho thời gian đến và rời đi của \(n\) khách hàng trong một nhà hàng.

Số lượng khách hàng tối đa trong nhà hàng bất cứ lúc nào là bao nhiêu?

Input

• Dòng đầu vào đầu tiên có một số nguyên \(n\): số lượng khách hàng.
• Sau này, có \(n\) dòng mô tả khách hàng. Mỗi dòng có hai số nguyên \(a\) và \(b\): thời gian đến và rời của khách hàng.
• Bạn có thể giả định rằng tất cả thời gian đến và đi là khác nhau.

Output

• In một số nguyên: số lượng khách hàng tối đa.

Constraints

• \(1 \le n \le 2 \cdot 10^5\)
• \(1 \le a < b \le 10^9\)

Example

Sample input

3
5 8
2 4
3 9

Sample output

2

Bạn phải xử lý \(n\) nhiệm vụ. Mỗi nhiệm vụ có một khoảng thời gian và thời hạn, và bạn sẽ xử lý các nhiệm vụ theo thứ tự nào đó, từ cái này để cái khác. Phần thưởng của bạn cho một nhiệm vụ là \(d − f\) trong đó \(d\) là thời hạn của nó và \(f\) là thời gian hoàn thành của bạn. (Thời gian bắt đầu là \(0\) và bạn phải xử lý tất cả các nhiệm vụ ngay cả khi một nhiệm vụ sẽ mang lại phần thưởng âm.)

Phần thưởng tối đa của bạn là bao nhiêu nếu bạn hành động tối ưu?

Input

• Dòng đầu vào đầu tiên có một số nguyên \(n\): số lượng nhiệm vụ.
• Sau này, có \(n\) dòng mô tả các nhiệm vụ. Mỗi dòng có hai số nguyên \(a\) và \(d\): khoảng thời gian và thời hạn của nhiệm vụ.

Output

• In một số nguyên: phần thưởng tối đa.

Constraints

• \(1 \leq n \leq 2 \cdot 10 ^ 5\)
• \(1 \leq a, d \leq 10 ^ 6\)

Example

Sample input

3
6 10
8 15
5 12

Sample output

2

Có \(n\) cuốn sách, và Kotivalo và Justiina sẽ đọc tất cả chúng. Đối với mỗi cuốn sách, bạn biết thời gian cần thiết để đọc nó.

Cả hai đều đọc từng cuốn sách từ đầu đến cuối, và họ không thể đọc một cuốn sách cùng một lúc. Tổng thời gian tối thiểu cần thiết là bao nhiêu?

Input

• Dòng đầu vào đầu tiên có một số nguyên \(n\): số lượng cuốn sách.
• Dòng thứ hai có \(n\) số nguyên \(t_1,t_2,\ldots,t_n\): thời gian cần thiết để đọc mỗi cuốn sách.

Output

• In một số nguyên: tổng thời gian tối thiểu.

Constraints

• \(1 \leq n \leq 2 \cdot 10 ^ 5\)
• \(1 \leq t_i \leq 10 ^ 9\)

Example

Sample input

3
2 8 3

Sample output

16

Bạn được cho một mảng gồm \(n\) số nguyên và nhiệm vụ của bạn là tìm ba giá trị (tại các vị trí phân biệt) có tổng là \(x\).

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(x\): kích thước mảng và tổng mong muốn.
• Dòng thứ hai có \(n\) số nguyên \(a_1,a_2,\ldots,a_n\): các giá trị của mảng.

Output

• In ba số nguyên: vị trí của các giá trị. Nếu có một số lời giải, bạn có thể in bất kỳ lời giải nào trong số đó. Nếu không có lời giải nào, in IMPOSSIBLE.

Constraints

• \(1 \leq n \leq 5000\)
• \(1 \leq x, a_i \leq 10 ^ 9\)

Example

Sample input

4 8
2 7 5 1

Sample output

1 3 4

Bạn được cho một mảng gồm \(n\) số nguyên và nhiệm vụ của bạn là tìm bốn giá trị (tại các vị trí phân biệt) có tổng là \(x\).

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(x\): kích thước mảng và tổng mong muốn.
• Dòng thứ hai có \(n\) số nguyên \(a_1,a_2,\ldots,a_n\): các giá trị của mảng.

Output

• In bốn số nguyên: vị trí của các giá trị. Nếu có một số lời giải, bạn có thể in bất kỳ lời giải nào trong số đó. Nếu không có lời giải nào, in IMPOSSIBLE.

Constraints

• \(1 \leq n \leq 1000\)
• \(1 \leq x, a_i \leq 10 ^ 9\)

Example

Sample input

8 15
3 2 5 8 1 3 2 3

Sample output

2 4 6 7

Cho một mảng gồm \(n\) số nguyên, nhiệm vụ của bạn là với mỗi vị trí của mảng, tìm vị trí gần nhất bên trái của nó mà có giá trị nhỏ hơn.

Input

• Dòng đầu vào đầu tiên có một số nguyên \(n\): kích thước của mảng.
• Dòng thứ hai có n số nguyên \(x_1,x_2,\ldots,x_n\): các giá trị của mảng.

Output

• In \(n\) số nguyên: vị trí gần nhất nhỏ hơn cho mỗi vị trí trong mảng. Nếu không có, in \(0\).

Constraints

• \(1 \leq n \leq 2 \cdot 10 ^ 5\)
• \(1 \leq x_i \leq 10 ^ 9\)

Example

Sample input

8
2 5 1 4 8 3 2 5

Sample output

0 1 0 3 4 3 3 7

Trong một lễ hội phim, \(n\) bộ phim sẽ được chiếu. Câu lạc bộ phim của Syrjälä bao gồm \(k\) thành viên, tất cả sẽ tham dự lễ hội phim.

Bạn biết thời gian bắt đầu và kết thúc của mỗi bộ phim. Tổng số phim tối đa mà các thành viên câu lạc bộ có thể xem hoàn toàn là bao nhiêu nếu họ hành động tối ưu?

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(k\): số lượng phim và thành viên câu lạc bộ.
• Sau này, có \(n\) dòng mô tả các bộ phim. Mỗi dòng có hai số nguyên \(a\) và \(b\): thời gian bắt đầu và kết thúc của một bộ phim.

Output

• In một số nguyên: tổng số bộ phim tối đa.

Constraints

• \(1 \le k \le n \le 2 \cdot 10^5\)
• \(1 \le a < b \le 10^9\)

Example

Sample input

5 2
1 5
8 10
3 6
2 5
6 9

Sample output

4

Cho một mảng gồm \(n\) số nguyên, nhiệm vụ của bạn là tìm tổng giá trị lớn nhất trong một đoạn con liên tiếp với độ dài giữa \(a\) và \(b\).

Input

• Dòng đầu vào đầu tiên có ba số nguyên \(n\), \(a\) và \(b\): kích thước của mảng và độ dài tối thiểu và tối đa của đoạn con.
• Dòng thứ hai có \(n\) số nguyên \(x_1, x_2, \ldots, x_n\): các giá trị mảng.

Output

• In một số nguyên: tổng đoạn con lớn nhất.

Constraints

• \(1 \le n \le 2 \cdot 10^5\)
• \(1 \le a \le b \le n\)
• \(-10^9 \le x_i \le 10^9\)

Example

8 1 2
-1 3 -2 5 3 -5 2 2

8