Emilia and her brother Alex meet up with a lot of friends in the park to play table tennis together. Since there is only one table, they play round-the-table which is everybody's favourite.
The rules are simple: There are $$$\ell \geq 2$$$ kids queueing up on the left side and $$$r \geq 1$$$ kids queueing up on the right side of the table. The first kid on the left side starts with the ball. Whoever has the ball hits it over the net onto the opposite side and runs around the table to join the queue at the opposite side. This is repeated until the first mistake.
Visualization of the first sample. During Hit $$$1$$$ and $$$5$$$, and during Hit $$$3$$$ and $$$7$$$, we observe the same pairing. After $$$8$$$ hits we end up in the initial state again and cannot observe any new pairing afterwards. Therefore, there are $$$6$$$ different pairings we will see in total. Emilia, Alex, and their friends play this game all the time and are so good that they can go on almost forever without making any mistake. After some time, Emilia notices that she has never faced Alex, meaning that they have never been at the front of opposite queues at the same time. She wonders if this will ever happen in this round. Curious about this, she starts keeping track which pairings have already faced each other.
How many different pairings has she counted after the ball went over the net $$$10^{10^{100}}$$$ times?
The input consist of:
- One line with two integers $$$\ell$$$ and $$$r$$$ ($$$2 \leq \ell \leq 10^{9}$$$ and $$$1 \leq r \leq 10^{9}$$$), the number of players on the left and right side of the table, respectively.
Output the number of different pairings Emilia counts.
2 2
6
2 3
10
3 2
5
5 2
14
The university of Bithampton is served by exactly one bus line. On its way to the city centre, it serves several stops at which students may exit. Every student has a fixed bus stop where they want to exit.
It is Friday afternoon, $$$4$$$ PM, and as always, all the students want to go home, leading to quite a long queue at the bus stop. Fortunately, the bus line is served in regular intervals, with the first bus arriving at $$$4$$$ PM.
Whenever a bus arrives at the university, everyone in the queue tries to enter the bus, which makes the buses very crowded. This has led to numerous complaints where people tried to exit buses but were unable to because of the sheer amount of people. As a consequence, the bus company decided that at every stop which someone in the bus has as destination, everyone in the bus must exit it. Those who want to travel further enter again. For every time a passenger enters or exits the bus, the bus needs to wait $$$w$$$ seconds.
To offer the best service, the bus company wants to minimize the maximum time it takes anybody from 4 PM until they reach their destination. For each bus, the bus driver can decide how many people from the front of the queue enter the bus. The number of people that can enter a bus is unlimited. Help the bus drivers make the optimal decisions to achieve the company's goal.
The input consists of:
- One line with four integers $$$n$$$, $$$b$$$, $$$r$$$, and $$$w$$$ ($$$1\leq n, b \leq 10^5$$$, $$$1\leq r, w \leq 10^6$$$), the number of passengers, the number of bus stops, the time between the arrival of two buses at the university, and the delay for exiting and entering.
- One line with $$$b$$$ integers $$$d_{i}$$$ ($$$1 \le d_{i}, \sum d_{i} \leq 10^6$$$), the travel time from the $$$(i-1)$$$th bus stop to the $$$i$$$th bus stop (the $$$0$$$th bus stop is the university).
- One line with $$$n$$$ integers $$$t_{i}$$$ ($$$1 \leq t_{i} \leq b$$$), indicating that the destination of the $$$i$$$th person in line is the $$$t_i$$$th bus stop.
Output the minimum number of seconds until every person in line has exited at their destination.
3 3 20 12 2 22 3 1
18
4 2 1 103 21 2 2 1
27
5 3 3 32 2 13 3 2 1 1
17
In the first example, it is optimal to let everyone board the first bus. The first boarding takes 3 seconds. Then, the bus drives for 2 seconds to get to the bus stop 1. After 3 seconds, everybody exited and after another 2 seconds, the people continuing their journey are back on the bus. After 2 more seconds, they arrive at the next stop where it takes 2 seconds for everybody to exit and one second for the remaining person to get back on the bus. After 2 more seconds, the bus arrives at the final destination where it takes one second for the last person to exit.
In the second example, it is optimal to use one bus per person.
In the third example, it is optimal to assign the first two passengers to one bus. Everybody else gets their own bus.
There is a game board with $$$n$$$ holes arranged in a long row. These holes are numbered from $$$1$$$ to $$$n$$$ from left to right. Initially the $$$i$$$th hole contains $$$a_i$$$ stones. Note that this setup differs from the usual Congklak game, where the game board consists of two rows and one large hole at each end.
Now Bill will play $$$t$$$ games where each game goes as follows:
Bill starts the game at the first hole, holding one new stone in his hand. He then moves along the game board from hole $$$1$$$ to hole $$$n$$$. At each hole $$$i$$$, he first checks how many stones are currently in the hole, and depending on the result he performs exactly one of the following two actions:
- If the hole is empty, he drops one stone into it. Next, he checks how many stones are still in his hand. If his hand is empty, the game stops. Otherwise, he moves his hand to hole $$$i+1$$$ next and repeats the steps.
- If there is at least one stone in the hole, he also drops one stone into it. Next, he checks how many stones are still in his hand. If his hand is empty, he takes out all the stones from hole $$$i$$$ into his hand. Regardless of whether or not his hand was empty, he moves his hand to hole $$$i+1$$$ next and repeats the steps.
Bill challenges Alice to predict in advance the number of stones in every hole after playing exactly $$$t$$$ games. Note that the game board is not reset after playing a game, i.e. the initial configuration of the second game is the same as the configuration when the first game ends.
The input consists of:
- One line with two integers $$$n$$$ and $$$t$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq t \leq 10^{12}$$$), the number of holes and the number of games.
- One line with $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^{12}$$$), where $$$a_i$$$ describes the initial number of stones in the $$$i$$$th hole.
Output $$$n$$$ integers, the $$$i$$$th of which is the number of stones in hole $$$i$$$ after playing $$$t$$$ games.
7 11 3 2 0 1 0 5
0 4 0 1 2 1 5
4 41000000000000 1 2 3
1 3 0 5
In the first sample, Bill plays exactly one game. The figure below visualizes the steps performed during this game.
In the second sample, the initial number of stones per hole is $$$[1000000000000, 1, 2, 3]$$$. The number of stones per hole after each game is:
- $$$[0, 2, 3, 4]$$$
- $$$[1, 2, 3, 4]$$$
- $$$[0, 3, 0, 5]$$$
- $$$[1, 3, 0, 5]$$$
In the Grid City of Perpendicular Cycling (GCPC for short), cars have never been popular. Instead, everyone uses various kinds of bicycles to make their way around the city. This is not the only feature of GCPC. Following an ancient city design used in different places since at least 2600 BC, all streets are going in one of the cardinal directions (i.e. either north/south or east/west) and therefore only meet at right angles.
The city council is planning on adding a new bike path surrounding the entire city to accommodate the strong demand for good cycling infrastructure. This new bike path should respect the historic grid system and should therefore only consist of segments parallel to one of the cardinal directions.
In order to minimize the construction cost and also the travel time for cyclists, the council wants this new bike path to be as short as possible. The council already prepared the outline of the city but now needs help in finding such a shortest bike path. For simplicity, you may assume that the bike path has width zero and may have distance zero to any point on the outline of the city.
Illustration of the first sample. The gray area represents the city and the black contour an optimal bike path. The given bike path has length $$$20$$$. It can be shown that there is no shorter one that satisfies the requirements. The input consists of:
- One line with an integer $$$n$$$ ($$$4 \leq n \leq 10^5$$$), the number of points of the outline of the city.
- $$$n$$$ lines, each with two integers $$$x$$$ and $$$y$$$ ($$$1 \leq x,y \leq 10^9$$$), the coordinates of the points.
- The points of the city's outline are given in counterclockwise order.
- Two consecutive points have either the same x-coordinate or the same y-coordinate.
- No three consecutive points are collinear.
- The outline of the city does not intersect itself.
Output an integer $$$m$$$ ($$$m\leq n$$$), the number of points of the bike path, followed by $$$m$$$ lines containing the coordinates of the bike path in counterclockwise order. Note that two consecutive points must have either the same x-coordinate or the same y-coordinate, and that no three consecutive points may be collinear.
If there are multiple valid solutions, you may output any one of them.
81 23 23 45 45 17 17 51 5
6 7 5 1 5 1 2 5 2 5 1 7 1
81 14 14 33 33 42 42 21 2
8 4 3 3 3 3 4 2 4 2 2 1 2 1 1 4 1
121 31 22 22 13 13 24 24 33 33 42 42 3
12 4 3 3 3 3 4 2 4 2 3 1 3 1 2 2 2 2 1 3 1 3 2 4 2
You are the engineer in charge of designing a wheel for a new space rover. As you do not have enough time to reinvent the wheel, you decide to copy your predecessor's work and make only one small change.
Looking at the plan, you notice that your predecessor's wheel has the shape of a convex polygon for structural reasons. It is well known that wheels with a larger perimeter roll farther per rotation, so surely they must be superior. You attempt to increase the perimeter by as much as possible by moving a single point on the outside of the wheel. While experimenting, you notice that wheels do not seem to work if they are non-convex or if there is an internal angle below $$$90$$$ degrees.
What is the maximum possible achievable increase in the perimeter of the wheel without violating the above restrictions?
Visualization of the first sample. Point $$$3$$$ is moved to $$$(5.5, 3.5)$$$, increasing the perimeter by $$$\approx 1.59488$$$. The input consists of:
- One line with an integer $$$n$$$ ($$$4 \leq n \leq 10^5$$$), the number of points of the wheel.
- $$$n$$$ lines, each with two integers $$$x$$$ and $$$y$$$ ($$$\left| x \right|, \left| y \right| \leq 10^5$$$), the coordinates of the points.
The points are given in counterclockwise order and form a convex polygon with no internal angle below $$$90$$$ degrees. Note that the convex polygon may contain collinear points, but no two points are at the same position.
Output the maximum possible absolute increase of the perimeter of the wheel.
Your answer should have an absolute or relative error of at most $$$10^{-6}$$$.
51 14 14 33 51 4
1.594883917346
70 -43 -35 -23 2-6 -2-6 -4-2 -4
3.151142198203
40 01 01 10 1
0.000000000000
Felix has ordered a large rectangular pizza for his birthday party. He only quickly went to the kitchen to grab some plates and cutlery, and when he came back his guests had already started helping themselves to various parts of the pizza. The pizza, which originally was made up of $$$h\times w$$$ square pieces of equal size, is now missing some of these pieces:
Illustration of the first sample case, with a division into squares of side length $$$2$$$. To ensure that the distribution of the rest of the pizza proceeds in a much more orderly fashion, Felix wants to divide up the remaining pizza into larger square shaped areas. Felix can only cut along the grid lines and cannot rearrange any parts of the pizza. Each square should have the same side length, which should be as large as possible in order to minimize the number of plates needed.
Find this largest possible side length. Note that an answer always exists because the pizza can always be divided into $$$1\times 1$$$ squares.
The input consists of:
- One line with two integers $$$h$$$ and $$$w$$$ ($$$1 \le h,w \le 2500$$$), the height and width of the grid.
- $$$h$$$ lines, each with a string of length $$$w$$$ consisting of '#' (denoting pizza pieces that are still there) and '.' (denoting pizza pieces that have already been taken).
Output an integer, the largest possible side length such that the remaining pizza can be divided into squares of that side length.
4 7####...####.##.######.####..
2
3 5#############..
1
3 5.##..#######.##
1
5 13....###..........###..###..######..###..###.....###..###.........
3
You have been tasked with creating a list of very secure passwords to be distributed to the users at the Generating Cool Passwords Company. Therefore, given an integer $$$n$$$, generate exactly $$$n$$$ passwords which each satisfy the following criteria:
- Each password consists of at least $$$8$$$ and at most $$$12$$$ printable ASCII characters with code between $$$33$$$ (!) and $$$126$$$ ( ) inclusive. See figure below for an overview of these.
- Each password contains at least one lowercase letter a-z, at least one uppercase letter A-Z, at least one digit 0-9 and at least one special symbol (any character that is neither a digit nor a lowercase or uppercase letter).
All the non-whitespace printable ASCII characters. The four relevant character classes are highlighted in different colours. Of course, the passwords should not be too similar to each other. Specifically, for every pair of passwords from your list it must be true that they are distinct and that moreover it is not possible to get one from the other by inserting, modifying or deleting a single character. Formally, the edit distance of any two passwords must be at least $$$2$$$.
The input consists of:
- One line with an integer $$$n$$$ ($$$1 \le n \le 1000$$$), the number of passwords to create.
Output $$$n$$$ lines, each with one password according to the rules above. The passwords must have pairwise edit distance at least $$$2$$$. If there is more than one solution, any one of them will be accepted.
3
haXXor@1337 hunTer2!!! abcABC123#@$
2
3');DRoP TABLEteams;2
It has happened! You found a match! Excitedly, your match Hannah and you have decided to have a morning stroll together. Since the two of you live in different cities, you decide to meetup at a train station.
Getting to your respective cities' train station is no problem. However, the ongoing renovations of the national train network heavily impact the available connections. Some of them are not available at all, and some others are only one-way. This makes it uncertain whether you can meet up at all.
Visualization of the third sample. Hannah starts from station $$$4$$$, and you start from station $$$1$$$. You can both reach station $$$3$$$ for your meet-up. You have found a list of the available train connections online. A train station is suitable for your meet-up if both Hannah and you can reach it. Determine whether there is a suitable train station or whether it is necessary to move the morning stroll to another day.
The input consists of:
- One line with two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 10^5$$$, $$$0 \leq m \leq 10^5$$$), the number of train stations and train connections, respectively.
- $$$m$$$ lines, each with two integers $$$x$$$ and $$$y$$$ ($$$1 \leq x, y \leq n$$$, $$$x \neq y$$$), denoting a direct train connection from train station $$$x$$$ to train station $$$y$$$.
- One line with two integers $$$a$$$ and $$$b$$$ ($$$1 \leq a,b \leq n$$$, $$$a \neq b$$$), the train stations you and Hannah start from, respectively.
If no suitable train station exists, output "no".
Otherwise, output "yes", followed by the train station. If there are multiple valid solutions, you may output any one of them.
3 21 32 31 2
yes 3
3 22 12 31 3
no
4 41 22 12 34 31 4
yes 3
On a small volcanic island far away from any major landmass, the Grand Council for Painless Cycling (GCPC) is facing regular complaints about the bad quality of the bike path network. Their budget is limited, but they would like to improve the situation for all the cyclists on their island. A survey helped to determine the most common destinations of the cyclists. The GCPC expects that the cyclists are satisfied with the bike path replacements if there is a way to cycle between any two destinations using only newly replaced bike paths. In order not to unduly favour any of the villages, the Council has decided that a maximum of $$$7$$$ destinations per village should be taken into account.
Illustration of the second sample. Village $$$1$$$ consists of Junctions $$$1$$$, $$$2$$$, $$$3$$$, and $$$4$$$, Village $$$2$$$ consists only of junction $$$5$$$, and Village $$$3$$$ consists of the remaining junctions. Junctions that are destinations are coloured red. There is one main cyclic bike path going around the volcano. On its way, it traverses every village on the island exactly once. Each village may have additional bike paths. How much does the GCPC have to spend at least in order to replace bike paths to connect all destinations via new paths?
The input consists of:
- One line with four integers $$$n$$$, $$$m$$$, $$$v$$$ and $$$k$$$ ($$$3\leq n\leq 5000$$$, $$$n \leq m \leq 20\,000$$$, $$$3 \leq v \leq n$$$, $$$1 \leq k \leq n$$$), the number of junctions, the number of bike paths, the number of villages, and the number of destinations.
- One line with $$$v$$$ integers $$$u_i$$$ ($$$1 \leq u_i$$$, $$$\sum_{i=1}^v u_i = n$$$), the $$$i$$$th of which describes the number of junctions in village $$$i$$$.
- $$$m$$$ lines each containing three integers $$$a$$$, $$$b$$$ and $$$c$$$ ($$$1 \leq a,b \leq n$$$, $$$1 \leq c \leq 10^9$$$), describing a bidirectional bike path between junction $$$a$$$ and junction $$$b$$$ with a replacement cost of $$$c$$$.
- One line with $$$k$$$ distinct integers $$$t$$$ ($$$1 \leq t \leq n$$$), the junctions that have to be connected by the replaced bike paths.
Additionally, the following is guaranteed:
- Village $$$1$$$ consists of junctions $$$1,\dots, u_1$$$, village $$$2$$$ consists of junctions $$$u_1 + 1, \dots, u_1 + u_2$$$, and so on. The last village consists of junctions $$$1+ \sum_{i = 1}^{v-1} u_i , \dots, n$$$. Within each village, it is possible to travel between any pair of junctions without leaving the village.
- There is a bike path between junctions $$$\sum_{i=1}^{j} u_i$$$ and $$$1 + \sum_{i=1}^{j} u_i$$$ for each $$$1 \leq j \leq v-1$$$, as well as a bike path between junctions $$$n$$$ and $$$1$$$. There are no other bike paths between different villages.
- There is at most one bike path between each pair of junctions and no bike path connects a junction to itself.
- In each village there are at most $$$7$$$ junctions that need to be part of the improved cycling network.
Output the minimum cost which allows replacing bike paths such that every trip between any two destinations can be done using only newly replaced paths.
3 3 3 31 1 12 1 52 3 41 3 32 1 3
7
8 10 3 64 1 31 2 32 4 21 3 53 4 24 5 35 6 28 6 36 7 27 8 28 1 12 3 1 7 6 8
12
Due to further and further advancements in technology and space exploration, humanity is sending probes to more planets and moons than ever before. One of these probes is currently residing on Phobos, one of the two Martian moons. This probe transmits binary data back to Earth but it can only do so in short time frames every few hours. Its fast orbit combined with its small size and close proximity to Mars means that Mars blocks radio waves most of the time by physically being in between the probe and Earth. During one time frame of data transmission, one large packet of $$$n$$$ binary bits is transmitted, exactly the amount possible within the time frame.
The probe has already been deployed for a few years, so mechanical problems have started to pile up. A recent and very problematic change has been the unreliability of the onboard clock, likely caused by the large and frequent temperature fluctuations ranging from about $$$-112^\circ$$$ to $$$-4^\circ$$$ Celsius. As a result, the probe has been transmitting data packets at incorrect times, when radio waves cannot reach Earth. To mitigate this, the probe is now sending its data packets multiple times in succession.
Even though this has led to Earth receiving $$$n$$$ bits of data, researchers are not able to determine the start and end of the data packet, making the data useless. The received data consists of a possibly empty suffix, followed by a prefix of the sent data, totalling to exactly $$$n$$$ bits. For example, if the original packet was "00101001", the received data might be "00100101".
You are to write software to encode the data before transmission into a message of the same length, such that you can decode it after receiving the mangled packet. Luckily, the engineering department has managed to improve the design of the receiving antenna, increasing the signal-to-noise ratio so you are now able to use an alphabet of three distinguishable symbols for radio transmission instead of only two.
Your program will be run twice for each test case. In the first pass, your program will be given a binary string to encode. In the second pass, your program will be given your encoded string from the first pass, which may have been modified as explained above. Decode this string to restore the input from the first pass.
A testing tool is provided to help develop your solution.
The input consists of:
- One line with either "Encode" or "Decode", depending on the action you are to perform.
- One line with an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$), the size of the data packet.
- One line with a string $$$s$$$ of $$$n$$$ characters, the data packet.
In the encoding pass, this string consists of the symbols '0' and '1'.
In the decoding pass, this string will be a cyclic rotation of your ternary string. In other words, this string is the string you printed in the encoding pass, potentially modified to reflect how this data packet might have been received on Earth, as described in the statement.
In the encoding pass, output the encoded string of length $$$n$$$ using the symbols '0', '1', and '2'.
In the decoding pass, output the original binary string, the data packet from the encoding pass.
For compatibility with the Codeforces platform, your solution runs in interactive mode against a jury program. A poorly implemented interaction may result in Idleness limit exceeded or Runtime Error instead of Wrong Answer. To handle input and output correctly, do not attempt to read extra data from the input. After finishing your output, don't forget to print a newline character and flush your output.
Encode 3 001
002
Decode 3 200
001
Encode 4 0100
2100
Decode 4 2100
0100
In the first sample, the encoded ternary string "002" was received as "200".
In the second sample, the encoded ternary string was received exactly the way it was encoded.
Skyscrapers is a grid logic puzzle in which numbers from $$$1$$$ to $$$n$$$ have to be placed into an $$$n\times n$$$ grid. Each number needs to appear exactly once in each row and column. These numbers are to be thought of as skyscrapers which are the respective number of units tall. The rows and columns may have clue numbers on either end which describe the number of visible skyscrapers when looking down that row or column from that position, where taller buildings block the view of any shorter buildings behind them.
Illustration of Sample Output 1. Two buildings (1 and 5) are visible from the left and two buildings (4 and 5) are visible from the right. In this problem we consider only a single row of a Skyscrapers grid which has clue numbers on both ends. Find out whether it is possible to place the skyscrapers from $$$1$$$ to $$$n$$$ in this row to satisfy both clues, and if so, find a valid placement.
The input consists of:
- One line with three integers $$$n$$$, $$$a$$$ and $$$b$$$ ($$$2 \le n \le 1000$$$, $$$1 \le a,b \le n$$$), the length of the row and the clues on the left and right.
If a valid placement exists, output "yes", followed by $$$n$$$ distinct integers $$$h_1,\dots,h_n$$$ ($$$1 \le h_i \le n$$$ for each $$$i$$$), the building heights from left to right.
If there are multiple valid solutions, you may output any one of them.
If no valid placement exists, output "no".
5 2 2
yes 1 5 2 3 4
5 3 4
no
10 3 4
yes 4 1 8 5 3 10 6 9 7 2
4 1 4
yes 4 3 2 1
9 1 1
no
6 2 1
yes 5 3 1 2 4 6
Alexander works at his company's HR department. As the working hours at his company are very flexible, the employees are allowed to work as many hours or as few as they want (within the legal constraints of course). The monthly salary for each employee thus depends on the time spent working. Therefore, one of Alexander's monthly tasks is to collect the times each employee has worked on any given day, so that he can calculate and pay out the employees salaries every month.
Unfortunately, today one of his colleagues forgot to record her lunch break and cannot remember how much time she spent on her break. As Alexander does not want to put his colleague at a disadvantage, he wants to use the legally required minimum break time for his calculations.
While calculating the total time his coworker spent at work is easy, correctly calculating the legally required minimum break time can be tricky. Can you help Alexander determine the minimum time his coworker must have spent at lunch today? Note that the time spent at work is the time spent working plus the time spent in break.
The input consists of:
- One line with an integer $$$t$$$ ($$$0\leq t\leq 1440$$$), the number of minutes spent at work today.
Output a single non-negative integer, the minimum number of minutes spent in break to make the work time legal.
495
30
360
0
540
30
0
0
To defend itself against you, the magic bobcat (as the name suggests) tries to hurt you in unconventional ways. When it attacks, it casts a number of magic spells. Each spell is cast with a particular potential, which can be expressed as a natural number.$$$^{\text{∗}}$$$ If you get hit with spells that have the potentials $$$p_1, p_2, \dots, p_n$$$, then the pain that you will feel from them is $$$\mathtt{mex}(\{p_1, p_2, \dots, p_n\})$$$, where $$$\mathtt{mex}$$$ denotes the Minimum Excluded Value.$$$^{\text{†}}$$$ Note that the spells do not hurt you immediately. Only after all spells are cast will you feel the pain based on the $$$\mathtt{mex}$$$ of their potentials.
To protect yourself, you bring a shield which can, also through magic, deflect the spells. Your shield has an activation duration $$$d$$$, which means that when you activate the shield, the next $$$d$$$ spells do not hit you. Afterwards, the shield must regenerate its magic and cannot be activated for the following $$$d$$$ spells. Apart from that, you can activate the shield as often as you want. To ensure that you give the magic bobcat a good scare, the mayor requested that you sneak up to it. As the bobcat would spot the glow of your activated magic shield, the earliest time you can activate the shield is when you stand before the culprit, right before it casts the first spell.
Illustration of Sample 3. The numbers in the boxes indicate the potentials of the spells. In this example, your shield's activation duration is $$$d = 2$$$. By activating the shield right before the 5th, 9th, and 14th spell, you block the spells underlined in green. You cannot activate your shield for the spells that are underlined with a dashed red line, because it is regenerating its magic at these times. You must now devise a tactic to sustain as little pain as possible. From studying the previous encounters with magic bobcats, you know the potentials of the spells that will be cast against you. What is the minimum pain you can receive from them if you activate your shield optimally?
$$$^{\text{∗}}$$$For the purposes of this task, the natural numbers are defined as $$$\mathbb N = \{0, 1, 2, \dots\}$$$.
$$$^{\text{†}}$$$Given a set $$$S \subseteq \mathbb N, S \ne \mathbb N$$$, $$$\mathtt{mex}(S)$$$ is the smallest number $$$m \in \mathbb N$$$ that is not contained in $$$S$$$.
The input consists of:
- One line with two integers $$$n$$$ and $$$d$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq d \leq n$$$), the number of spells and the activation duration of your shield.
- One line with $$$n$$$ integers $$$p_1, \dots, p_n$$$ ($$$0 \leq p_i \lt n$$$), the potentials of the $$$n$$$ spells.
Output a single integer, the minimum pain you can receive from the spells.
5 10 1 0 1 0
0
5 20 1 0 1 0
2
14 28 1 1 0 0 2 0 1 2 1 0 6 4 2
2
4 20 1 2 0
1
In the first sample, you can activate the shield for the first spell, let it regenerate its magic for the second, activate it again for the third, regenerate for the fourth, and activate again on the fifth spell. This means that only the two spells of potential $$$1$$$ hit you. As $$$\mathtt{mex}(\{1, 1\}) = 0$$$, you receive $$$0$$$ pain.
In the second sample, no matter how you activate your shield, during the time it regenerates, a spell of potential $$$0$$$ and a spell of potential $$$1$$$ hit you. Thus, the $$$\mathtt{mex}$$$ of the spells that hit you is at least $$$2$$$. This amount of pain can be achieved by not using your shield at all.
In the third sample, use the shield as depicted in the statement above. Then the spells that hit you have potentials $$$8$$$, $$$1$$$, $$$1$$$, $$$0$$$, $$$0$$$, $$$1$$$, $$$0$$$, $$$6$$$, and $$$4$$$. The $$$\mathtt{mex}$$$ of these potentials is $$$2$$$. It can be shown that there is no way of activating your shield so that the $$$\mathtt{mex}$$$ of the potentials of the remaining spells is $$$0$$$ or $$$1$$$.
In the fourth sample, recall that you cannot activate your shield any earlier than right before the first spell. Thus, you cannot block both spells of potential $$$0$$$. Instead, by blocking the second and third spell, all spells that hit you have potential $$$0$$$.