Sorting and Searching Jul 02, 2025

Problem A. Distinct Numbers

Time Limit 1000 ms
Mem Limit 524288 kB

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 x1 , x2 , … , xn .

​ ​ ​

Output

Print one integers: the number of distinct values.

Constraints

1 ≤ n ≤ 2 ⋅ 105
1 ≤ xi ≤ 109
​

Example

Input Output

5 2
2 3 2 2 3

Page 1 of 35
-
 Sorting and Searching Jul 02, 2025

Problem B. Apartments
Time Limit 1000 ms
Mem Limit 524288 kB

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 a1 , a2 , … , an : the desired apartment size of each
​ ​

applicant. If the desired size of an applicant is x, they will accept any apartment whose
size is between x − k and x + k .

The last line contains m integers b1 , b2 , … , bm : the size of each apartment.

​ ​ ​

Output

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

Constraints

1 ≤ n, m ≤ 2 ⋅ 105
0 ≤ k ≤ 109
1 ≤ ai , bi ≤ 109
​ ​

Example

Input Output

4 3 5 2
60 45 80 60
30 60 75

Page 2 of 35
-
 Sorting and Searching Jul 02, 2025

Problem C. Ferris Wheel

Time Limit 1000 ms
Mem Limit 524288 kB

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 p1 , p2 , … , pn : the weight of each child.

​ ​ ​

Output

Print one integer: the minimum number of gondolas.

Constraints

1 ≤ n ≤ 2 ⋅ 105
1 ≤ x ≤ 109
1 ≤ pi ≤ x
​

Example

Input Output

4 10 3
7 2 3 9

Page 3 of 35
-
 Sorting and Searching Jul 02, 2025

Problem D. Concert Tickets

Time Limit 1000 ms
Mem Limit 524288 kB

There are n concert tickets available, each with a certain price. Then, m customers arrive,
one after another.

Each customer announces the maximum price they are willing to pay for a ticket, and
after this, they will get a ticket with the nearest possible price such that it does not exceed
the maximum price.

Input

The first input line contains integers n and m: the number of tickets and the number of
customers.

The next line contains n integers h1 , h2 , … , hn : the price of each ticket.

​ ​ ​

The last line contains m integers t1 , t2 , … , tm : the maximum price for each customer in
​ ​ ​

the order they arrive.

Output

Print, for each customer, the price that they will pay for their ticket. After this, the ticket
cannot be purchased again.

If a customer cannot get any ticket, print −1.

Constraints

1 ≤ n, m ≤ 2 ⋅ 105
1 ≤ hi , ti ≤ 109
​ ​

Example

Input Output

5 3 3
5 3 7 8 5 8
4 8 3 -1

Page 4 of 35
-
 Sorting and Searching Jul 02, 2025

Problem E. Restaurant Customers

Time Limit 1000 ms
Mem Limit 524288 kB

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

What was the maximum number of customers in the restaurant at any time?

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.

Output

Print one integer: the maximum number of customers.

Constraints

1 ≤ n ≤ 2 ⋅ 105
1 ≤ a < b ≤ 109

Example

Input Output

3 2
5 8
2 4
3 9

Page 5 of 35
-
 Sorting and Searching Jul 02, 2025

Problem F. Movie Festival

Time Limit 1000 ms
Mem Limit 524288 kB

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.

Output

Print one integer: the maximum number of movies.

Constraints

1 ≤ n ≤ 2 ⋅ 105
1 ≤ a < b ≤ 109

Example

Input Output

3 2
3 5
4 9
5 8

Page 6 of 35
-
 Sorting and Searching Jul 02, 2025

Problem G. Sum of Two Values

Time Limit 1000 ms
Mem Limit 524288 kB

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 a1 , a2 , … , an : the array values.

​ ​ ​

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 IMPOSSIBLE .

Constraints

1 ≤ n ≤ 2 ⋅ 105
1 ≤ x, ai ≤ 109
​

Example

Input Output

4 8 2 4
2 7 5 1

Page 7 of 35
-
 Sorting and Searching Jul 02, 2025

Problem H. Maximum Subarray Sum

Time Limit 1000 ms
Mem Limit 524288 kB

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 x1 , x2 , … , xn : the array values.

​ ​ ​

Output

Print one integer: the maximum subarray sum.

Constraints

1 ≤ n ≤ 2 ⋅ 105
−109 ≤ xi ≤ 109
​

Example

Input Output

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

Page 8 of 35
-
 Sorting and Searching Jul 02, 2025

Problem I. Stick Lengths

Time Limit 1000 ms
Mem Limit 524288 kB

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: p1 , p2 , … , pn : the lengths of the sticks.

​ ​ ​

Output

Print one integer: the minimum total cost.

Constraints

1 ≤ n ≤ 2 ⋅ 105
1 ≤ pi ≤ 109
​

Example

Input Output

5 5
2 3 1 5 2

Page 9 of 35
-
 Sorting and Searching Jul 02, 2025

Problem J. Missing Coin Sum

Time Limit 1000 ms
Mem Limit 524288 kB

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 line has an integer n: the number of coins.

The second line has n integers x1 , x2 , … , xn : the value of each coin.

​ ​ ​

Output

Print one integer: the smallest coin sum.

Constraints

1 ≤ n ≤ 2 ⋅ 105
1 ≤ xi ≤ 109
​

Example

Input Output

5 6
2 9 1 2 7

Page 10 of 35
-
 Sorting and Searching Jul 02, 2025

Problem K. Collecting Numbers

Time Limit 1000 ms
Mem Limit 524288 kB

You are given an array that contains each number between 1 … 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 line has an integer n: the array size.

The next line has n integers x1 , x2 , … , xn : the numbers in the array.

​ ​ ​

Output

Print one integer: the number of rounds.

Constraints

1 ≤ n ≤ 2 ⋅ 105

Example

Input Output

5 3
4 2 1 5 3

Page 11 of 35
-
 Sorting and Searching Jul 02, 2025

Problem L. Collecting Numbers II

Time Limit 1000 ms
Mem Limit 524288 kB

You are given an array that contains each number between 1 … 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 x1 , x2 , … , xn : 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.

Output

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

Constraints

1 ≤ n, m ≤ 2 ⋅ 105
1 ≤ a, b ≤ n

Example

Input Output

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

Page 12 of 35
-
 Sorting and Searching Jul 02, 2025

Problem M. Playlist
Time Limit 1000 ms
Mem Limit 524288 kB

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 k1 , k2 , … , kn : the id number of each song.

​ ​ ​

Output

Print the length of the longest sequence of unique songs.

Constraints

1 ≤ n ≤ 2 ⋅ 105
1 ≤ ki ≤ 109
​

Example

Input Output

8 5
1 2 1 3 2 7 4 2

Page 13 of 35
-
 Sorting and Searching Jul 02, 2025

Problem N. Towers
Time Limit 1000 ms
Mem Limit 524288 kB

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 contains n integers k1 , k2 , … , kn : the sizes of the cubes.

​ ​ ​

Output

Print one integer: the minimum number of towers.

Constraints

1 ≤ n ≤ 2 ⋅ 105
1 ≤ ki ≤ 109
​

Example

Input Output

5 2
3 8 2 1 5

Page 14 of 35
-
 Sorting and Searching Jul 02, 2025

Problem O. Traffic Lights

Time Limit 1000 ms
Mem Limit 524288 kB

There is a street of length x whose positions are numbered 0, 1, … , 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 p1 , p2 , … , pn : the position of each set of traffic
​ ​ ​

lights. Each position is distinct.

Output

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

Constraints

1 ≤ x ≤ 109
1 ≤ n ≤ 2 ⋅ 105
0 < pi < x
​

Example

Input Output

8 3 5 3 3
3 6 2

Page 15 of 35
-
 Sorting and Searching Jul 02, 2025

Problem P. Distinct Values Subarrays

Time Limit 1000 ms
Mem Limit 524288 kB

Given an array of n integers, count the number of subarrays where each element is
dictinct.

Input

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

The second line has n integers x1 , x2 , … , xn : the array contents.

​ ​ ​

Output

Print the number of subarrays with distinct elements.

Constraints

1 ≤ n ≤ 2 ⋅ 105
1 ≤ xi ≤ 109
​

Example

Input Output

4 8
1 2 1 3

Explanation: The subarrays are [1] (two times), [2], [3], [1, 2], [1, 3], [2, 1] and [2, 1, 3].

Page 16 of 35
-
 Sorting and Searching Jul 02, 2025

Problem Q. Distinct Values Subsequences

Time Limit 1000 ms
Mem Limit 524288 kB

Given an array of n integers, count the number of subsequences where each element is
dictinct.

A subsequence is a sequence of array elements from left to right that may have gaps.

Input

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

The second line has n integers x1 , x2 , … , xn : the array contents.

​ ​ ​

Output

Print the number of subsequences with distinct elements. The answer can be large, so
print it modulo 109 + 7.

Constraints

1 ≤ n ≤ 2 ⋅ 105
1 ≤ xi ≤ 109
​

Example

Input Output

4 11
1 2 1 3

Explanation: The subsequences are [1] (two times), [2], [3], [1, 2], [1, 3] (two times), [2, 1],
[2, 3], [1, 2, 3] and [2, 1, 3].

Page 17 of 35
-
 Sorting and Searching Jul 02, 2025

Problem R. Josephus Problem I

Time Limit 1000 ms
Mem Limit 524288 kB

Consider a game where there are n children (numbered 1, 2, … , n) in a circle. During the
game, every other 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.

Output

Print n integers: the removal order.

Constraints

1 ≤ n ≤ 2 ⋅ 105

Example

Input Output

7 2 4 6 1 5 3 7

Page 18 of 35
-
 Sorting and Searching Jul 02, 2025

Problem S. Josephus Problem II

Time Limit 1000 ms
Mem Limit 524288 kB

Consider a game where there are n children (numbered 1, 2, … , 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 .

Output

Print n integers: the removal order.

Constraints

1 ≤ n ≤ 2 ⋅ 105
0 ≤ k ≤ 109

Example

Input Output

7 2 3 6 2 7 5 1 4

Page 19 of 35
-
 Sorting and Searching Jul 02, 2025

Problem T. Nested Ranges Check

Time Limit 1000 ms
Mem Limit 524288 kB

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 ≤ c and d ≤ 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.

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).

Constraints

1 ≤ n ≤ 2 ⋅ 105
1 ≤ x < y ≤ 109

Example

Input Output

4 1 0 0 0
1 6 0 1 0 1
2 4
4 8
3 6

Page 20 of 35
-
 Sorting and Searching Jul 02, 2025

Problem U. Nested Ranges Count

Time Limit 1000 ms
Mem Limit 524288 kB

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 ≤ c and d ≤ 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.

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.

Constraints

1 ≤ n ≤ 2 ⋅ 105
1 ≤ x < y ≤ 109

Example

Input Output

4 2 0 0 0
1 6 0 1 0 1
2 4
4 8
3 6

Page 21 of 35
-
 Sorting and Searching Jul 02, 2025

Problem V. Room Allocation

Time Limit 1000 ms
Mem Limit 524288 kB

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.

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, … , k . You can print any valid solution.

Constraints

1 ≤ n ≤ 2 ⋅ 105
1 ≤ a ≤ b ≤ 109

Example

Input Output

3 2
1 2 1 2 1
2 4
4 4

Page 22 of 35
-
 Sorting and Searching Jul 02, 2025

Problem W. Factory Machines

Time Limit 1000 ms
Mem Limit 524288 kB

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 k1 , k2 , … , kn : the time needed to make a product using each
​ ​ ​

machine.

Output

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

Constraints

1 ≤ n ≤ 2 ⋅ 105
1 ≤ t ≤ 109
1 ≤ ki ≤ 109
​

Example

Input Output

3 7 8
3 2 5

Explanation: Machine 1 makes two products, machine 2 makes four products and machine
3 makes one product.

Page 23 of 35
-
 Sorting and Searching Jul 02, 2025

Problem X. Tasks and Deadlines

Time Limit 1000 ms
Mem Limit 524288 kB

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.

Output

Print one integer: the maximum reward.

Constraints

1 ≤ n ≤ 2 ⋅ 105
1 ≤ a, d ≤ 106

Example

Input Output

3 2
6 10
8 15
5 12

Page 24 of 35
-
 Sorting and Searching Jul 02, 2025

Problem Y. Reading Books

Time Limit 1000 ms
Mem Limit 524288 kB

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 t1 , t2 , … , tn : the time required to read each book.
​ ​ ​

Output

Print one integer: the minimum total time.

Constraints

1 ≤ n ≤ 2 ⋅ 105
1 ≤ ti ≤ 109
​

Example

Input Output

3 16
2 8 3

Page 25 of 35
-
 Sorting and Searching Jul 02, 2025

Problem Z. Sum of Three Values

Time Limit 1000 ms
Mem Limit 524288 kB

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 a1 , a2 , … , an : the array values.

​ ​ ​

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 IMPOSSIBLE .

Constraints

1 ≤ n ≤ 5000
1 ≤ x, ai ≤ 109
​

Example

Input Output

4 8 1 3 4
2 7 5 1

Page 26 of 35
-
 Sorting and Searching Jul 02, 2025

Problem AA. Sum of Four Values

Time Limit 1000 ms
Mem Limit 524288 kB

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 a1 , a2 , … , an : the array values.

​ ​ ​

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 IMPOSSIBLE .

Constraints

1 ≤ n ≤ 1000
1 ≤ x, ai ≤ 109
​

Example

Input Output

8 15 2 4 6 7
3 2 5 8 1 3 2 3

Page 27 of 35
-
 Sorting and Searching Jul 02, 2025

Problem AB. Nearest Smaller Values

Time Limit 1000 ms
Mem Limit 524288 kB

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 x1 , x2 , … , xn : the array values.

​ ​ ​

Output

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

Constraints

1 ≤ n ≤ 2 ⋅ 105
1 ≤ xi ≤ 109
​

Example

Input Output

8 0 1 0 3 4 3 3 7
2 5 1 4 8 3 2 5

Page 28 of 35
-
 Sorting and Searching Jul 02, 2025

Problem AC. Subarray Sums I

Time Limit 1000 ms
Mem Limit 524288 kB

Given an array of n 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 next line has n integers a1 , a2 , … , an : the contents of the array.

​ ​ ​

Output

Print one integer: the required number of subarrays.

Constraints

1 ≤ n ≤ 2 ⋅ 105
1 ≤ x, ai ≤ 109
​

Example

Input Output

5 7 3
2 4 1 2 7

Page 29 of 35
-
 Sorting and Searching Jul 02, 2025

Problem AD. Subarray Sums II

Time Limit 1000 ms
Mem Limit 524288 kB

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 next line has n integers a1 , a2 , … , an : the contents of the array.

​ ​ ​

Output

Print one integer: the required number of subarrays.

Constraints

1 ≤ n ≤ 2 ⋅ 105
−109 ≤ x, ai ≤ 109
​

Example

Input Output

5 7 2
2 -1 3 5 -2

Page 30 of 35
-
 Sorting and Searching Jul 02, 2025

Problem AE. Subarray Divisibility

Time Limit 1000 ms
Mem Limit 524288 kB

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 a1 , a2 , … , an : the contents of the array.

​ ​ ​

Output

Print one integer: the required number of subarrays.

Constraints

1 ≤ n ≤ 2 ⋅ 105
−109 ≤ ai ≤ 109
​

Example

Input Output

5 1
3 1 2 7 4

Page 31 of 35
-
 Sorting and Searching Jul 02, 2025

Problem AF. Subarray Distinct Values

Time Limit 1000 ms
Mem Limit 524288 kB

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 x1 , x2 , … , xn : the contents of the array.

​ ​ ​

Output

Print one integer: the number of subarrays.

Constraints

1 ≤ k ≤ n ≤ 2 ⋅ 105
1 ≤ xi ≤ 109
​

Example

Input Output

5 2 10
1 2 3 1 1

Page 32 of 35
-
 Sorting and Searching Jul 02, 2025

Problem AG. Array Division

Time Limit 1000 ms
Mem Limit 524288 kB

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 contains two integers n and k : the size of the array and the number of
subarrays in the division.

The next line contains n integers x1 , x2 , … , xn : the contents of the array.

​ ​ ​

Output

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

Constraints

1 ≤ n ≤ 2 ⋅ 105
1≤k≤n
1 ≤ xi ≤ 109
​

Example

Input Output

5 3 8
2 4 7 3 5

Explanation: An optimal division is [2, 4], [7], [3, 5] where the sums of the subarrays are
6, 7, 8. The largest sum is the last sum 8.

Page 33 of 35
-
 Sorting and Searching Jul 02, 2025

Problem AH. Movie Festival II

Time Limit 1000 ms
Mem Limit 524288 kB

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.

Output

Print one integer: the maximum total number of movies.

Constraints

1 ≤ k ≤ n ≤ 2 ⋅ 105
1 ≤ a < b ≤ 109

Example

Input Output

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

Page 34 of 35
-
 Sorting and Searching Jul 02, 2025

Problem AI. Maximum Subarray Sum II

Time Limit 1000 ms
Mem Limit 524288 kB

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 x1 , x2 , … , xn : the array values.

​ ​ ​

Output

Print one integer: the maximum subarray sum.

Constraints

1 ≤ n ≤ 2 ⋅ 105
1≤a≤b≤n
−109 ≤ xi ≤ 109
​

Example

Input Output

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

Page 35 of 35
-