CSES Problem Set: Sorting and Searching
A. Distinct Numbers
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a list of $$$n$$$ integers, and your task is to calculate the number of distinct values in the list.

Input

The first input line has an integer $$$n$$$: the number of values.

The second line has $$$n$$$ integers $$$x_1,x_2,\dots,x_n$$$.

Constraints:

  • $$$1 \le n \le 2 \cdot 10^5$$$
  • $$$1 \le x_i \le 10^9$$$
Output

Print one integer: the number of distinct values.

Example
Input
5
2 3 2 2 3
Output
2

B. Apartments
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ applicants and $$$m$$$ free apartments. Your task is to distribute the apartments so that as many applicants as possible will get an apartment.

Each applicant has a desired apartment size, and they will accept any apartment whose size is close enough to the desired size.

Input

The first input line has three integers $$$n$$$, $$$m$$$, and $$$k$$$: the number of applicants, the number of apartments, and the maximum allowed difference.

The next line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$: the desired apartment size of each applicant. If the desired size of an applicant is $$$x$$$, he or she will accept any apartment whose size is between $$$x−k$$$ and $$$x+k$$$.

The last line contains $$$m$$$ integers $$$b_1,b_2,\dots,b_m$$$: the size of each apartment.

Constraints:

  • $$$1 \le n,m \le 2\cdot 10^5$$$
  • $$$0 \le k \le 10^9$$$
  • $$$1 \le a_i,b_i \le 10^9$$$
Output

Print one integer: the number of applicants who will get an apartment.

Example
Input
4 3 5
60 45 80 60
30 60 75
Output
2

C. Ferris Wheel
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ children who want to go to a Ferris wheel, and your task is to find a gondola for each child.

Each gondola may have one or two children in it, and in addition, the total weight in a gondola may not exceed $$$x$$$. You know the weight of every child.

What is the minimum number of gondolas needed for the children?

Input

The first input line contains two integers $$$n$$$ and $$$x$$$: the number of children and the maximum allowed weight.

The next line contains $$$n$$$ integers $$$p_1,p_2,\dots,p_n$$$: the weight of each child.

Constraints:

  • $$$1 \le n \le 2\cdot 10^5$$$
  • $$$0 \le x \le 10^9$$$
  • $$$1 \le p_i \le x$$$
Output

Print one integer: the minimum number of gondolas.

Example
Input
4 10
7 2 3 9
Output
3

Statement is not available in English language
E. Restaurant Customers
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given the arrival and leaving times of $$$n$$$ customers in a restaurant.

What was the maximum number of customers?

Input

The first input line has an integer $$$n$$$: the number of customers.

After this, there are $$$n$$$ lines that describe the customers. Each line has two integers $$$a$$$ and $$$b$$$: the arrival and leaving times of a customer.

You may assume that all arrival and leaving times are distinct.

Constraints:

  • $$$1 \le n \le 2 \cdot 10^5$$$
  • $$$1 \le a \le b \le 10^9$$$
Output

Print one integer: the maximum number of customers.

Example
Input
3
5 8
2 4
3 9
Output
2

F. Movie Festival
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

In a movie festival $$$n$$$ movies will be shown. You know the starting and ending time of each movie. What is the maximum number of movies you can watch entirely?

Input

The first input line has an integer $$$n$$$: the number of movies.

After this, there are $$$n$$$ lines that describe the movies. Each line has two integers $$$a$$$ and $$$b$$$: the starting and ending times of a movie.

Constraints:

  • $$$1 \le n \le 2 \cdot 10^5$$$
  • $$$1 \le a \lt b \le 10^9$$$
Output

Print one integer: the maximum number of movies.

Example
Input
3
3 5
4 9
5 8
Output
2

G. Sum of Two Values
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array of $$$n$$$ integers, and your task is to find two values (at distinct positions) whose sum is $$$x$$$.

Input

The first input line has two integers $$$n$$$ and $$$x$$$: the array size and the target sum.

The second line has n integers $$$a_1,a_2,\dots, a_n$$$: the array values.

Constraints:

  • $$$2 \le n \le 2 \cdot 10^5$$$
  • $$$1 \le x,a_i \le 10^9$$$
Output

Print two integers: the positions of the values. If there are several solutions, you may print any of them. If there are no solutions, print $$$-1$$$.

Example
Input
4 8
2 7 5 1
Output
2 4

H. Maximum Subarray Sum
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an array of $$$n$$$ integers, your task is to find the maximum sum of values in a contiguous, nonempty subarray.

Input

The first input line has an integer n: the size of the array.

The second line has $$$n$$$ integers $$$x_1,x_2,\dots,x_n$$$: the array values.

Constraints:

  • $$$1 \le n \le 2\cdot 10^5$$$
  • $$$-10^9 \le x_i \le 10^9$$$
Output

Print one integer: the maximum subarray sum.

Example
Input
8
-1 3 -2 5 3 -5 2 2
Output
9

I. Stick Lengths
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ sticks with some lengths. Your task is to modify the sticks so that each stick has the same length.

You can either lengthen and shorten each stick. Both operations cost $$$x$$$ where $$$x$$$ is the difference between the new and original length.

What is the minimum total cost?

Input

The first input line contains an integer $$$n$$$: the number of sticks.

Then there are n integers: $$$p_1,p_2,\dots,p_n$$$: the lengths of the sticks.

Constraints:

  • $$$1 \le n \le 2 \cdot 10^5$$$
  • $$$1 \le p_i \le 10^9$$$
Output

Print one integer: the minimum total cost.

Example
Input
5
2 3 1 5 2
Output
5

J. Missing Coin Sum
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

You have $$$n$$$ coins with positive integer values. What is the smallest sum you cannot create using a subset of the coins?

Input

The first input line has an integer $$$n$$$: the number of coins.

The second line has n integers $$$x_1,x_2,\dots,x_n$$$: the value of each coin.

Constraints:

  • $$$1 \le n \le 2\cdot 10^5$$$
  • $$$1 \le x_i \le 10^9$$$
Output

Print one integer: the smallest coin sum.

Example
Input
5
2 9 1 2 7
Output
6

K. Collecting Numbers
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array that contains each number between $$$1\dots n$$$ exactly once. Your task is to collect the numbers from $$$1$$$ to $$$n$$$ in increasing order.

On each round, you go through the array from left to right and collect as many numbers as possible. What will be the total number of rounds?

Input

The first input line has an integer $$$n$$$: the array size.

The second line has n integers $$$x_1,x_2,\dots,x_n$$$: the numbers in the array.

Constraints:

  • $$$1 \le n \le 2\cdot 10^5$$$
Output

Print one integer: the number of rounds.

Example
Input
5
4 2 1 5 3
Output
3

L. Collecting Numbers II
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array that contains each number between $$$1\dots n$$$ exactly once. Your task is to collect the numbers from $$$1$$$ to $$$n$$$ in increasing order.

On each round, you go through the array from left to right and collect as many numbers as possible.

Given $$$m$$$ operations that swap two numbers in the array, your task is to report the number of rounds after each operation.

Input

The first line has two integers $$$n$$$ and $$$m$$$: the array size and the number of operations.

The next line has $$$n$$$ integers $$$x_1,x_2,\dots,x_n$$$: the numbers in the array.

Finally, there are $$$m$$$ lines that describe the operations. Each line has two integers $$$a$$$ and $$$b$$$: the numbers at positions a and b are swapped.

Constraints:

  • $$$1 \le n,m \le 2\cdot 10^5$$$
  • $$$1 \le a,b \le n$$$
Output

Print m integers: the number of rounds after each swap.

Example
Input
5 3
4 2 1 5 3
2 3
1 5
2 3
Output
2
3
4

M. Playlist
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a playlist of a radio station since its establishment. The playlist has a total of $$$n$$$ songs.

What is the longest sequence of successive songs where each song is unique?

Input

The first input line contains an integer $$$n$$$: the number of songs.

The next line has $$$n$$$ integers $$$k_1,k_2,\dots,k_n$$$: the id number of each song.

Constraints:

  • $$$1 \le n \le 2\cdot 10^5$$$
  • $$$1 \le k_i \le 10^9$$$
Output

Print the length of the longest sequence of unique songs.

Example
Input
8
1 2 1 3 2 7 4 2
Output
5

N. Towers
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$n$$$ cubes in a certain order, and your task is to build towers using them. Whenever two cubes are one on top of the other, the upper cube must be smaller than the lower cube.

You must process the cubes in the given order. You can always either place the cube on top of an existing tower, or begin a new tower. What is the minimum possible number of towers?

Input

The first input line contains an integer $$$n$$$: the number of cubes.

The next line has $$$n$$$ integers $$$k_1,k_2,\dots,k_n$$$: the size of the cubes.

Constraints:

  • $$$1 \le n \le 2\cdot 10^5$$$
  • $$$1 \le k_i \le 10^9$$$
Output

Print one integer: the minimum number of towers.

Example
Input
5
3 8 2 1 5
Output
2

O. Traffic Lights
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a street of length $$$x$$$ whose positions are numbered $$$0,1,\dots,x$$$. Initially there are no traffic lights, but $$$n$$$ sets of traffic lights are added to the street one after another.

Your task is to calculate the length of the longest passage without traffic lights after each addition.

Input

The first input line contains two integers $$$x$$$ and $$$n$$$: the length of the street and the number of sets of traffic lights.

Then, the next line contains $$$n$$$ integers $$$p_1,p_2,\dots,p_n$$$: the position of each set of traffic lights. Each position is distinct.

Constraints:

  • $$$1 \le x \le 10^9$$$
  • $$$1 \le n \le 2\cdot 10^5$$$
  • $$$0 \lt p_i \lt x$$$
Output

Print the length of the longest passage without traffic lights after each addition.

Example
Input
8 3
3 6 2
Output
5 3 3

P. Josephus Problem I
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

Consider a game where there are $$$n$$$ children (numbered $$$1,2,\dots,n$$$) in a circle. During the game, every second child is removed from the circle, until there are no children left. In which order will the children be removed?

Input

The only input line has an integer n.

Constraints:

  • $$$1 \le n \le 2\cdot 10^5$$$
Output

Print $$$n$$$ integers: the removal order.

Example
Input
7
Output
2 4 6 1 5 3 7

Q. Josephus Problem II
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

Consider a game where there are $$$n$$$ children (numbered $$$1,2,\dots,n$$$) in a circle. During the game, repeatedly $$$k$$$ children are skipped and one child is removed from the circle. In which order will the children be removed?

Input

The only input line has two integers $$$n$$$ and $$$k$$$.

Constraints:

  • $$$1 \le n \le 2\cdot 10^5$$$
  • $$$1 \le k \le 10^9$$$
Output

Print $$$n$$$ integers: the removal order.

Example
Input
7 2
Output
3 6 2 7 5 1 4

R. Nested Ranges Check
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

Given $$$n$$$ ranges, your task is to determine for each range if it contains some other range and if some other range contains it.

Range $$$[a,b]$$$ contains range $$$[c,d]$$$ if $$$a\le c$$$ and $$$d\le b$$$.

Input

The first input line has an integer $$$n$$$: the number of ranges.

After this, there are $$$n$$$ lines that describe the ranges. Each line has two integers $$$x$$$ and $$$y$$$: the range is $$$[x,y]$$$.

You may assume that no range appears more than once in the input.

Constraints:

  • $$$1 \le n \le 2\cdot 10^5$$$
  • $$$1 \le x \lt y \le 10^9$$$
Output

First print a line that describes for each range (in the input order) if it contains some other range (1) or not (0).

Then print a line that describes for each range (in the input order) if some other range contains it (1) or not (0).

Example
Input
4
1 6
2 4
4 8
3 6
Output
1 0 0 0 
0 1 0 1

S. Nested Ranges Count
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

Given $$$n$$$ ranges, your task is to count for each range how many other ranges it contains and how many other ranges contain it.

Range $$$[a,b]$$$ contains range $$$[c,d]$$$ if $$$a\le c$$$ and $$$d\le b$$$.

Input

The first input line has an integer $$$n$$$: the number of ranges.

After this, there are $$$n$$$ lines that describe the ranges. Each line has two integers $$$x$$$ and $$$y$$$: the range is $$$[x,y]$$$.

You may assume that no range appears more than once in the input.

Constraints:

  • $$$1 \le n \le 2\cdot 10^5$$$
  • $$$1 \le x \lt y \le 10^9$$$
Output

First print a line that describes for each range (in the input order) how many other ranges it contains.

Then print a line that describes for each range (in the input order) how many other ranges contain it.

Example
Input
4
1 6
2 4
4 8
3 6
Output
2 0 0 0 
0 1 0 1

T. Room Allocation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a large hotel, and $$$n$$$ customers will arrive soon. Each customer wants to have a single room.

You know each customer's arrival and departure day. Two customers can stay in the same room if the departure day of the first customer is earlier than the arrival day of the second customer.

What is the minimum number of rooms that are needed to accommodate all customers? And how can the rooms be allocated?

Input

The first input line contains an integer $$$n$$$: the number of customers.

Then there are $$$n$$$ lines, each of which describes one customer. Each line has two integers $$$a$$$ and $$$b$$$: the arrival and departure day.

Constraints:

  • $$$1 \le n \le 2\cdot 10^5$$$
  • $$$1 \le a \le b \le 10^9$$$
Output

Print first an integer $$$k$$$: the minimum number of rooms required.

After that, print a line that contains the room number of each customer in the same order as in the input. The rooms are numbered $$$1,2,\dots,k$$$. You can print any valid solution.

Example
Input
3
1 2
2 4
4 4
Output
2
1 2 1

U. Factory Machines
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A factory has $$$n$$$ machines which can be used to make products. Your goal is to make a total of $$$t$$$ products.

For each machine, you know the number of seconds it needs to make a single product. The machines can work simultaneously, and you can freely decide their schedule.

What is the shortest time needed to make $$$t$$$ products?

Input

The first input line has two integers $$$n$$$ and $$$t$$$: the number of machines and products.

The next line has $$$n$$$ integers $$$k_1,k_2,\dots,k_n$$$: the time needed to make a product using each machine.

Constraints:

  • $$$1 \le n \le 2\cdot 10^5$$$
  • $$$1 \le t \le 10^9$$$
  • $$$1 \le k_i \le 10^9$$$
Output

Print one integer: the minimum time needed to make $$$t$$$ products.

Example
Input
3 7
3 2 5
Output
8

V. Tasks and Deadlines
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You have to process $$$n$$$ tasks. Each task has a duration and a deadline, and you will process the tasks in some order one after another. Your reward for a task is $$$d−f$$$ where $$$d$$$ is its deadline and $$$f$$$ is your finishing time. (The starting time is $$$0$$$, and you have to process all tasks even if a task would yield negative reward.)

What is your maximum reward if you act optimally?

Input

The first input line has an integer $$$n$$$: the number of tasks.

After this, there are $$$n$$$ lines that describe the tasks. Each line has two integers $$$a$$$ and $$$d$$$: the duration and deadline of the task.

Constraints:

  • $$$1 \le n \le 2\cdot 10^5$$$
  • $$$1 \le a,d \le 10^6$$$
Output

Print one integer: the maximum reward.

Example
Input
3
6 10
8 15
5 12
Output
2

W. Reading Books
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ books, and Kotivalo and Justiina are going to read them all. For each book, you know the time it takes to read it.

They both read each book from beginning to end, and they cannot read a book at the same time. What is the minimum total time required?

Input

The first input line has an integer $$$n$$$: the number of books.

The second line has n integers $$$t_1,t_2,\dots,t_n$$$: the time required to read each book.

Constraints:

  • $$$1 \le n \le 2\cdot 10^5$$$
  • $$$1 \le t_i \le 10^9$$$
Output

Print one integer: the minimum total time.

Example
Input
3
2 8 3
Output
16

X. Sum of Three Values
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array of $$$n$$$ integers, and your task is to find three values (at distinct positions) whose sum is $$$x$$$.

Input

The first input line has two integers $$$n$$$ and $$$x$$$: the array size and the target sum.

The second line has $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$: the array values.

Constraints:

  • $$$3 \le n \le 5000$$$
  • $$$1 \le x,a_i \le 10^9$$$
Output

Print three integers: the positions of the values. If there are several solutions, you may print any of them. If there are no solutions, print $$$-1$$$.

Example
Input
1 3 4
Output
3 4 1

Y. Sum of Four Values
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array of $$$n$$$ integers, and your task is to find four values (at distinct positions) whose sum is $$$x$$$.

Input

The first input line has two integers $$$n$$$ and $$$x$$$: the array size and the target sum.

The second line has $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$: the array values.

Constraints:

  • $$$4 \le n \le 1000$$$
  • $$$1 \le x,a_i \le 10^9$$$
Output

Print four integers: the positions of the values. If there are several solutions, you may print any of them. If there are no solutions, print $$$-1$$$.

Example
Input
8 15
3 2 5 8 1 3 2 3
Output
2 4 6 7

Z. Nearest Smaller Values
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an array of $$$n$$$ integers, your task is to find for each array position the nearest position to its left having a smaller value.

Input

The first input line has an integer $$$n$$$: the size of the array.

The second line has $$$n$$$ integers $$$x_1,x_2,\dots,x_n$$$: the array values.

Constraints:

  • $$$1 \le n \le 2\cdot 10^5$$$
  • $$$1 \le x,a_i \le 10^9$$$
Output

Print $$$n$$$ integers: for each array position the nearest position with a smaller value. If there is no such position, print $$$0$$$.

Example
Input
8
2 5 1 4 8 3 2 5
Output
0 1 0 3 4 3 3 7

ZA. Subarray Sums I
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an array of $$$n$$$ $$$\textbf{positive}$$$ integers, your task is to count the number of subarrays having sum $$$x$$$.

Input

The first input line has two integers $$$n$$$ and $$$x$$$: the size of the array and the target sum $$$x$$$.

The second line has $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$: the contents of the array.

Constraints:

  • $$$1 \le n \le 2 \cdot 10^5$$$
  • $$$1 \le x,a_i \le 10^9$$$
Output

Print one integer: the required number of subarrays.

Example
Input
5 7
2 4 1 2 7
Output
3

ZB. Subarray Sums II
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an array of $$$n$$$ integers, your task is to count the number of subarrays having sum $$$x$$$.

Input

The first input line has two integers $$$n$$$ and $$$x$$$: the size of the array and the target sum $$$x$$$.

The second line has $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$: the contents of the array.

Constraints:

  • $$$1 \le n \le 2 \cdot 10^5$$$
  • $$$-10^9 \le x,a_i \le 10^9$$$
Output

Print one integer: the required number of subarrays.

Example
Input
5 7
2 -1 3 5 -2
Output
2

ZC. Subarray Divisibility
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an array of $$$n$$$ integers, your task is to count the number of subarrays where the sum of values is divisible by $$$n$$$.

Input

The first input line has an integer $$$n$$$: the size of the array.

The next line has $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$: the contents of the array.

Constraints:

  • $$$1 \le n \le 2 \cdot 10^5$$$
  • $$$-10^9 \le a_i \le 10^9$$$
Output

Print one integer: the required number of subarrays.

Example
Input
5
3 1 2 7 4
Output
1

ZD. Subarray Distinct Values
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an array of $$$n$$$ integers, your task is to calculate the number of subarrays that have at most $$$k$$$ distinct values.

Input

The first input line has two integers $$$n$$$ and $$$k$$$.

The next line has $$$n$$$ integers $$$x_1,x_2,\dots,x_n$$$: the contents of the array.

Constraints:

  • $$$1 \le k \le n \le 2 \cdot 10^5$$$
  • $$$1 \le x_i \le 10^9$$$
Output

Print one integer: the number of subarrays.

Example
Input
5 2
1 2 3 1 1
Output
10

ZE. Array Division
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array containing $$$n$$$ positive integers.

Your task is to divide the array into $$$k$$$ subarrays so that the maximum sum in a subarray is as small as possible.

Input

The first input line has two integers $$$n$$$ and $$$k$$$.

The next line has $$$n$$$ integers $$$x_1,x_2,\dots,x_n$$$: the contents of the array.

Constraints:

  • $$$1 \le k \le n \le 2 \cdot 10^5$$$
  • $$$1 \le x_i \le 10^9$$$
Output

Print one integer: the maximum sum in a subarray in the optimal division.

Example
Input
5 3
2 4 7 3 5
Output
8

ZF. Sliding Median
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array of $$$n$$$ integers. Your task is to calculate the median of each window of $$$k$$$ elements, from left to right.

The median is the middle element when the elements are sorted. If the number of elements is even, there are two possible medians and we assume that the median is the smaller of them.

Input

The first input line contains two integers $$$n$$$ and $$$k$$$: the number of elements and the size of the window.

Then there are $$$n$$$ integers $$$x_1,x_2,\dots,x_n$$$: the contents of the array.

Output

Print $$$n−k+1$$$ values: the medians.

Example
Input
8 3
2 4 3 5 8 1 2 1
Output
3 4 5 5 2 1

ZG. Sliding Cost
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array of $$$n$$$ integers. Your task is to calculate for each window of $$$k$$$ elements, from left to right, the minimum total cost of making all elements equal.

You can increase or decrease each element with cost $$$x$$$ where $$$x$$$ is the difference between the new and the original value. The total cost is the sum of such costs.

Input

The first input line contains two integers n and k: the number of elements and the size of the window.

Then there are $$$n$$$ integers $$$x_1,x_2,\dots,x_n$$$: the contents of the array.

Output

Output $$$n−k+1$$$ values: the costs.

Example
Input
8 3
2 4 3 5 8 1 2 1
Output
2 2 5 7 7 1

ZH. Movie Festival II
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In a movie festival, $$$n$$$ movies will be shown. Syrjälä's movie club consists of $$$k$$$ members, who will be all attending the festival.

You know the starting and ending time of each movie. What is the maximum total number of movies the club members can watch entirely if they act optimally?

Input

The first input line has two integers $$$n$$$ and $$$k$$$: the number of movies and club members.

After this, there are $$$n$$$ lines that describe the movies. Each line has two integers $$$a$$$ and $$$b$$$: the starting and ending time of a movie.

Constraints:

  • $$$1 \le k \le n \le 2 \cdot 10^5$$$
  • $$$1 \le a \lt b \le 10^9$$$
Output

Print one integer: the maximum total number of movies.

Example
Input
5 2
1 5
8 10
3 6
2 5
6 9
Output
4

ZI. Maximum Subarray Sum II
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an array of $$$n$$$ integers, your task is to find the maximum sum of values in a contiguous subarray with length between $$$a$$$ and $$$b$$$.

Input

The first input line has three integers $$$n$$$, $$$a$$$, and $$$b$$$: the size of the array and the minimum and maximum subarray length.

The second line has $$$n$$$ integers $$$x_1,x_2,\dots,x_n$$$: the array values

Constraints:

  • $$$1 \le n \le 2 \cdot 10^5$$$
  • $$$1 \le a \le b \le 2 n$$$
  • $$$1 \le x_i \le 10^9$$$
Output

Print one integer: the maximum subarray sum.

Example
Input
8 1 2
-1 3 -2 5 3 -5 2 2
Output
8