meetforever/GRPO_CL huggingface dataset:
user: We've got no test cases. A big olympiad is coming up. But the problemsetters' number one priority should be adding another problem to the round. 

The diameter of a multiset of points on the line is the largest distance between two points from this set. For example, the diameter of the multiset {1, 3, 2, 1} is 2.

Diameter of multiset consisting of one point is 0.

You are given n points on the line. What is the minimum number of points you have to remove, so that the diameter of the multiset of the remaining points will not exceed d?


-----Input-----

The first line contains two integers n and d (1 ≤ n ≤ 100, 0 ≤ d ≤ 100) — the amount of points and the maximum allowed diameter respectively.

The second line contains n space separated integers (1 ≤ x_{i} ≤ 100) — the coordinates of the points.


-----Output-----

Output a single integer — the minimum number of points you have to remove.


-----Examples-----
Input
3 1
2 1 4

Output
1

Input
3 0
7 7 7

Output
0

Input
6 3
1 3 4 6 9 10

Output
3



-----Note-----

In the first test case the optimal strategy is to remove the point with coordinate 4. The remaining points will have coordinates 1 and 2, so the diameter will be equal to 2 - 1 = 1.

In the second test case the diameter is equal to 0, so its is unnecessary to remove any points. 

In the third test case the optimal strategy is to remove points with coordinates 1, 9 and 10. The remaining points will have coordinates 3, 4 and 6, so the diameter will be equal to 6 - 3 = 3.
user: Small, but very brave, mouse Brain was not accepted to summer school of young villains. He was upset and decided to postpone his plans of taking over the world, but to become a photographer instead.

As you may know, the coolest photos are on the film (because you can specify the hashtag #film for such).

Brain took a lot of colourful pictures on colored and black-and-white film. Then he developed and translated it into a digital form. But now, color and black-and-white photos are in one folder, and to sort them, one needs to spend more than one hour!

As soon as Brain is a photographer not programmer now, he asks you to help him determine for a single photo whether it is colored or black-and-white.

Photo can be represented as a matrix sized n × m, and each element of the matrix stores a symbol indicating corresponding pixel color. There are only 6 colors:   'C' (cyan) 'M' (magenta) 'Y' (yellow) 'W' (white) 'G' (grey) 'B' (black) 

The photo is considered black-and-white if it has only white, black and grey pixels in it. If there are any of cyan, magenta or yellow pixels in the photo then it is considered colored.


-----Input-----

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 100) — the number of photo pixel matrix rows and columns respectively.

Then n lines describing matrix rows follow. Each of them contains m space-separated characters describing colors of pixels in a row. Each character in the line is one of the 'C', 'M', 'Y', 'W', 'G' or 'B'.


-----Output-----

Print the "#Black&White" (without quotes), if the photo is black-and-white and "#Color" (without quotes), if it is colored, in the only line.


-----Examples-----
Input
2 2
C M
Y Y

Output
#Color
Input
3 2
W W
W W
B B

Output
#Black&White
Input
1 1
W

Output
#Black&White
user: Sonya decided that having her own hotel business is the best way of earning money because she can profit and rest wherever she wants.

The country where Sonya lives is an endless line. There is a city in each integer coordinate on this line. She has $n$ hotels, where the $i$-th hotel is located in the city with coordinate $x_i$. Sonya is a smart girl, so she does not open two or more hotels in the same city.

Sonya understands that her business needs to be expanded by opening new hotels, so she decides to build one more. She wants to make the minimum distance from this hotel to all others to be equal to $d$. The girl understands that there are many possible locations to construct such a hotel. Thus she wants to know the number of possible coordinates of the cities where she can build a new hotel. 

Because Sonya is lounging in a jacuzzi in one of her hotels, she is asking you to find the number of cities where she can build a new hotel so that the minimum distance from the original $n$ hotels to the new one is equal to $d$.


-----Input-----

The first line contains two integers $n$ and $d$ ($1\leq n\leq 100$, $1\leq d\leq 10^9$) — the number of Sonya's hotels and the needed minimum distance from a new hotel to all others.

The second line contains $n$ different integers in strictly increasing order $x_1, x_2, \ldots, x_n$ ($-10^9\leq x_i\leq 10^9$) — coordinates of Sonya's hotels.


-----Output-----

Print the number of cities where Sonya can build a new hotel so that the minimum distance from this hotel to all others is equal to $d$.


-----Examples-----
Input
4 3
-3 2 9 16

Output
6

Input
5 2
4 8 11 18 19

Output
5



-----Note-----

In the first example, there are $6$ possible cities where Sonya can build a hotel. These cities have coordinates $-6$, $5$, $6$, $12$, $13$, and $19$.

In the second example, there are $5$ possible cities where Sonya can build a hotel. These cities have coordinates $2$, $6$, $13$, $16$, and $21$.
user: Vasya has an array of integers of length n.

Vasya performs the following operations on the array: on each step he finds the longest segment of consecutive equal integers (the leftmost, if there are several such segments) and removes it. For example, if Vasya's array is [13, 13, 7, 7, 7, 2, 2, 2], then after one operation it becomes [13, 13, 2, 2, 2].

Compute the number of operations Vasya should make until the array becomes empty, i.e. Vasya removes all elements from it.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 200 000) — the length of the array.

The second line contains a sequence a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9) — Vasya's array.


-----Output-----

Print the number of operations Vasya should make to remove all elements from the array.


-----Examples-----
Input
4
2 5 5 2

Output
2

Input
5
6 3 4 1 5

Output
5

Input
8
4 4 4 2 2 100 100 100

Output
3

Input
6
10 10 50 10 50 50

Output
4



-----Note-----

In the first example, at first Vasya removes two fives at the second and third positions. The array becomes [2, 2]. In the second operation Vasya removes two twos at the first and second positions. After that the array becomes empty.

In the second example Vasya has to perform five operations to make the array empty. In each of them he removes the first element from the array.

In the third example Vasya needs three operations. In the first operation he removes all integers 4, in the second — all integers 100, in the third — all integers 2.

In the fourth example in the first operation Vasya removes the first two integers 10. After that the array becomes [50, 10, 50, 50]. Then in the second operation Vasya removes the two rightmost integers 50, so that the array becomes [50, 10]. In the third operation he removes the remaining 50, and the array becomes [10] after that. In the last, fourth operation he removes the only remaining 10. The array is empty after that.
user: Limak is a grizzly bear who desires power and adoration. He wants to win in upcoming elections and rule over the Bearland.

There are n candidates, including Limak. We know how many citizens are going to vote for each candidate. Now i-th candidate would get a_{i} votes. Limak is candidate number 1. To win in elections, he must get strictly more votes than any other candidate.

Victory is more important than everything else so Limak decided to cheat. He will steal votes from his opponents by bribing some citizens. To bribe a citizen, Limak must give him or her one candy - citizens are bears and bears like candies. Limak doesn't have many candies and wonders - how many citizens does he have to bribe?


-----Input-----

The first line contains single integer n (2 ≤ n ≤ 100) - number of candidates.

The second line contains n space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 1000) - number of votes for each candidate. Limak is candidate number 1.

Note that after bribing number of votes for some candidate might be zero or might be greater than 1000.


-----Output-----

Print the minimum number of citizens Limak must bribe to have strictly more votes than any other candidate.


-----Examples-----
Input
5
5 1 11 2 8

Output
4

Input
4
1 8 8 8

Output
6

Input
2
7 6

Output
0



-----Note-----

In the first sample Limak has 5 votes. One of the ways to achieve victory is to bribe 4 citizens who want to vote for the third candidate. Then numbers of votes would be 9, 1, 7, 2, 8 (Limak would have 9 votes). Alternatively, Limak could steal only 3 votes from the third candidate and 1 vote from the second candidate to get situation 9, 0, 8, 2, 8.

In the second sample Limak will steal 2 votes from each candidate. Situation will be 7, 6, 6, 6.

In the third sample Limak is a winner without bribing any citizen.
user: You are given a string $s$, consisting of $n$ lowercase Latin letters.

A substring of string $s$ is a continuous segment of letters from $s$. For example, "defor" is a substring of "codeforces" and "fors" is not. 

The length of the substring is the number of letters in it.

Let's call some string of length $n$ diverse if and only if there is no letter to appear strictly more than $\frac n 2$ times. For example, strings "abc" and "iltlml" are diverse and strings "aab" and "zz" are not.

Your task is to find any diverse substring of string $s$ or report that there is none. Note that it is not required to maximize or minimize the length of the resulting substring.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 1000$) — the length of string $s$.

The second line is the string $s$, consisting of exactly $n$ lowercase Latin letters.


-----Output-----

Print "NO" if there is no diverse substring in the string $s$.

Otherwise the first line should contain "YES". The second line should contain any diverse substring of string $s$.


-----Examples-----
Input
10
codeforces

Output
YES
code

Input
5
aaaaa

Output
NO



-----Note-----

The first example has lots of correct answers. 

Please, restrain yourself from asking if some specific answer is correct for some specific test or not, these questions always lead to "No comments" answer.
user: The final round of Bayan Programming Contest will be held in Tehran, and the participants will be carried around with a yellow bus. The bus has 34 passenger seats: 4 seats in the last row and 3 seats in remaining rows.  [Image] 

The event coordinator has a list of k participants who should be picked up at the airport. When a participant gets on the bus, he will sit in the last row with an empty seat. If there is more than one empty seat in that row, he will take the leftmost one. 

In order to keep track of the people who are on the bus, the event coordinator needs a figure showing which seats are going to be taken by k participants. Your task is to draw the figure representing occupied seats.


-----Input-----

The only line of input contains integer k, (0 ≤ k ≤ 34), denoting the number of participants.


-----Output-----

Print the figure of a bus with k passengers as described in sample tests. Character '#' denotes an empty seat, while 'O' denotes a taken seat. 'D' is the bus driver and other characters in the output are for the purpose of beautifying the figure. Strictly follow the sample test cases output format. Print exactly six lines. Do not output extra space or other characters.


-----Examples-----
Input
9

Output
+------------------------+
|O.O.O.#.#.#.#.#.#.#.#.|D|)
|O.O.O.#.#.#.#.#.#.#.#.|.|
|O.......................|
|O.O.#.#.#.#.#.#.#.#.#.|.|)
+------------------------+

Input
20

Output
+------------------------+
|O.O.O.O.O.O.O.#.#.#.#.|D|)
|O.O.O.O.O.O.#.#.#.#.#.|.|
|O.......................|
|O.O.O.O.O.O.#.#.#.#.#.|.|)
+------------------------+
user: We'll define S(n) for positive integer n as follows: the number of the n's digits in the decimal base. For example, S(893) = 3, S(114514) = 6.

You want to make a consecutive integer sequence starting from number m (m, m + 1, ...). But you need to pay S(n)·k to add the number n to the sequence.

You can spend a cost up to w, and you want to make the sequence as long as possible. Write a program that tells sequence's maximum length.


-----Input-----

The first line contains three integers w (1 ≤ w ≤ 10^16), m (1 ≤ m ≤ 10^16), k (1 ≤ k ≤ 10^9).

Please, do not write the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.


-----Output-----

The first line should contain a single integer — the answer to the problem.


-----Examples-----
Input
9 1 1

Output
9

Input
77 7 7

Output
7

Input
114 5 14

Output
6

Input
1 1 2

Output
0
user: Polycarpus loves lucky numbers. Everybody knows that lucky numbers are positive integers, whose decimal representation (without leading zeroes) contain only the lucky digits x and y. For example, if x = 4, and y = 7, then numbers 47, 744, 4 are lucky.

Let's call a positive integer a undoubtedly lucky, if there are such digits x and y (0 ≤ x, y ≤ 9), that the decimal representation of number a (without leading zeroes) contains only digits x and y.

Polycarpus has integer n. He wants to know how many positive integers that do not exceed n, are undoubtedly lucky. Help him, count this number.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 10^9) — Polycarpus's number.


-----Output-----

Print a single integer that says, how many positive integers that do not exceed n are undoubtedly lucky.


-----Examples-----
Input
10

Output
10

Input
123

Output
113



-----Note-----

In the first test sample all numbers that do not exceed 10 are undoubtedly lucky.

In the second sample numbers 102, 103, 104, 105, 106, 107, 108, 109, 120, 123 are not undoubtedly lucky.
user: Iahub and his friend Floyd have started painting a wall. Iahub is painting the wall red and Floyd is painting it pink. You can consider the wall being made of a very large number of bricks, numbered 1, 2, 3 and so on. 

Iahub has the following scheme of painting: he skips x - 1 consecutive bricks, then he paints the x-th one. That is, he'll paint bricks x, 2·x, 3·x and so on red. Similarly, Floyd skips y - 1 consecutive bricks, then he paints the y-th one. Hence he'll paint bricks y, 2·y, 3·y and so on pink.

After painting the wall all day, the boys observed that some bricks are painted both red and pink. Iahub has a lucky number a and Floyd has a lucky number b. Boys wonder how many bricks numbered no less than a and no greater than b are painted both red and pink. This is exactly your task: compute and print the answer to the question. 


-----Input-----

The input will have a single line containing four integers in this order: x, y, a, b. (1 ≤ x, y ≤ 1000, 1 ≤ a, b ≤ 2·10^9, a ≤ b).


-----Output-----

Output a single integer — the number of bricks numbered no less than a and no greater than b that are painted both red and pink.


-----Examples-----
Input
2 3 6 18

Output
3


-----Note-----

Let's look at the bricks from a to b (a = 6, b = 18). The bricks colored in red are numbered 6, 8, 10, 12, 14, 16, 18. The bricks colored in pink are numbered 6, 9, 12, 15, 18. The bricks colored in both red and pink are numbered with 6, 12 and 18.
user: You came to the exhibition and one exhibit has drawn your attention. It consists of $n$ stacks of blocks, where the $i$-th stack consists of $a_i$ blocks resting on the surface.

The height of the exhibit is equal to $m$. Consequently, the number of blocks in each stack is less than or equal to $m$.

There is a camera on the ceiling that sees the top view of the blocks and a camera on the right wall that sees the side view of the blocks.$\text{Top View}$ 

Find the maximum number of blocks you can remove such that the views for both the cameras would not change.

Note, that while originally all blocks are stacked on the floor, it is not required for them to stay connected to the floor after some blocks are removed. There is no gravity in the whole exhibition, so no block would fall down, even if the block underneath is removed. It is not allowed to move blocks by hand either.


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \le n \le 100\,000$, $1 \le m \le 10^9$) — the number of stacks and the height of the exhibit.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le m$) — the number of blocks in each stack from left to right.


-----Output-----

Print exactly one integer — the maximum number of blocks that can be removed.


-----Examples-----
Input
5 6
3 3 3 3 3

Output
10
Input
3 5
1 2 4

Output
3
Input
5 5
2 3 1 4 4

Output
9
Input
1 1000
548

Output
0
Input
3 3
3 1 1

Output
1


-----Note-----

The following pictures illustrate the first example and its possible solution.

Blue cells indicate removed blocks. There are $10$ blue cells, so the answer is $10$.[Image]
user: Being a programmer, you like arrays a lot. For your birthday, your friends have given you an array a consisting of n distinct integers.

Unfortunately, the size of a is too small. You want a bigger array! Your friends agree to give you a bigger array, but only if you are able to answer the following question correctly: is it possible to sort the array a (in increasing order) by reversing exactly one segment of a? See definitions of segment and reversing in the notes.


-----Input-----

The first line of the input contains an integer n (1 ≤ n ≤ 10^5) — the size of array a.

The second line contains n distinct space-separated integers: a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 10^9).


-----Output-----

Print "yes" or "no" (without quotes), depending on the answer.

If your answer is "yes", then also print two space-separated integers denoting start and end (start must not be greater than end) indices of the segment to be reversed. If there are multiple ways of selecting these indices, print any of them.


-----Examples-----
Input
3
3 2 1

Output
yes
1 3

Input
4
2 1 3 4

Output
yes
1 2

Input
4
3 1 2 4

Output
no

Input
2
1 2

Output
yes
1 1



-----Note-----

Sample 1. You can reverse the entire array to get [1, 2, 3], which is sorted.

Sample 3. No segment can be reversed such that the array will be sorted.

Definitions

A segment [l, r] of array a is the sequence a[l], a[l + 1], ..., a[r].

If you have an array a of size n and you reverse its segment [l, r], the array will become:

a[1], a[2], ..., a[l - 2], a[l - 1], a[r], a[r - 1], ..., a[l + 1], a[l], a[r + 1], a[r + 2], ..., a[n - 1], a[n].
user: Dreamoon wants to climb up a stair of n steps. He can climb 1 or 2 steps at each move. Dreamoon wants the number of moves to be a multiple of an integer m. 

What is the minimal number of moves making him climb to the top of the stairs that satisfies his condition?


-----Input-----

The single line contains two space separated integers n, m (0 < n ≤ 10000, 1 < m ≤ 10).


-----Output-----

Print a single integer — the minimal number of moves being a multiple of m. If there is no way he can climb satisfying condition print  - 1 instead.


-----Examples-----
Input
10 2

Output
6

Input
3 5

Output
-1



-----Note-----

For the first sample, Dreamoon could climb in 6 moves with following sequence of steps: {2, 2, 2, 2, 1, 1}.

For the second sample, there are only three valid sequence of steps {2, 1}, {1, 2}, {1, 1, 1} with 2, 2, and 3 steps respectively. All these numbers are not multiples of 5.
user: Your security guard friend recently got a new job at a new security company. The company requires him to patrol an area of the city encompassing exactly N city blocks, but they let him choose which blocks. That is, your friend must walk the perimeter of a region whose area is exactly N blocks. Your friend is quite lazy and would like your help to find the shortest possible route that meets the requirements. The city is laid out in a square grid pattern, and is large enough that for the sake of the problem it can be considered infinite.


-----Input-----

Input will consist of a single integer N (1 ≤ N ≤ 10^6), the number of city blocks that must be enclosed by the route.


-----Output-----

Print the minimum perimeter that can be achieved.


-----Examples-----
Input
4

Output
8

Input
11

Output
14

Input
22

Output
20



-----Note-----

Here are some possible shapes for the examples:

[Image]
user: Like any unknown mathematician, Yuri has favourite numbers: $A$, $B$, $C$, and $D$, where $A \leq B \leq C \leq D$. Yuri also likes triangles and once he thought: how many non-degenerate triangles with integer sides $x$, $y$, and $z$ exist, such that $A \leq x \leq B \leq y \leq C \leq z \leq D$ holds?

Yuri is preparing problems for a new contest now, so he is very busy. That's why he asked you to calculate the number of triangles with described property.

The triangle is called non-degenerate if and only if its vertices are not collinear.


-----Input-----

The first line contains four integers: $A$, $B$, $C$ and $D$ ($1 \leq A \leq B \leq C \leq D \leq 5 \cdot 10^5$) — Yuri's favourite numbers.


-----Output-----

Print the number of non-degenerate triangles with integer sides $x$, $y$, and $z$ such that the inequality $A \leq x \leq B \leq y \leq C \leq z \leq D$ holds.


-----Examples-----
Input
1 2 3 4

Output
4

Input
1 2 2 5

Output
3

Input
500000 500000 500000 500000

Output
1



-----Note-----

In the first example Yuri can make up triangles with sides $(1, 3, 3)$, $(2, 2, 3)$, $(2, 3, 3)$ and $(2, 3, 4)$.

In the second example Yuri can make up triangles with sides $(1, 2, 2)$, $(2, 2, 2)$ and $(2, 2, 3)$.

In the third example Yuri can make up only one equilateral triangle with sides equal to $5 \cdot 10^5$.
user: You are given <var>Q</var> tuples of integers <var>(L_i, A_i, B_i, M_i)</var>. For each tuple, answer the following question. 
There is an arithmetic progression with L terms: s_0, s_1, s_2, ... , s_{L-1}.
The initial term is A, and the common difference is B. That is, s_i = A + B \times i holds.
Consider the integer obtained by concatenating the terms written in base ten without leading zeros. For example, the sequence 3, 7, 11, 15, 19 would be concatenated into 37111519. What is the remainder when that integer is divided by M?

-----Constraints-----
 - All values in input are integers.
 - 1 \leq L, A, B < 10^{18}
 - 2 \leq M \leq 10^9
 - All terms in the arithmetic progression are less than 10^{18}.

-----Input-----
Input is given from Standard Input in the following format:
L A B M

-----Output-----
Print the remainder when the integer obtained by concatenating the terms is divided by M.

-----Sample Input-----
5 3 4 10007

-----Sample Output-----
5563

Our arithmetic progression is 3, 7, 11, 15, 19, so the answer is 37111519 mod 10007, that is, 5563.