apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array a of length n. We define fa the following way:

- Initially fa = 0, M = 1;
- for every 2 ≤ i ≤ n if aM < ai then we set fa = fa + aM and then set M = i.

Calculate the sum of fa over all n! permutations of the array a modulo 109 + 7.

Note: two elements are considered different if their indices differ, so for every array a there are exactly n! permutations.

## Input Format
The first line contains integer n (1 ≤ n ≤  1 000 000) — the size of array a.

Second line contains n integers a1, a2, ..., an (1 ≤  ai ≤  109).

## Output Format
Print the only integer, the sum of fa over all n! permutations of the array a modulo 109 + 7.

## Examples
```input
2
1 3
```
```output
1
```
-----
```input
3
1 1 2
```
```output
4
```

## Note
For the second example all the permutations are:

- p = [1, 2, 3] : fa is equal to 1;
- p = [1, 3, 2] : fa is equal to 1;
- p = [2, 1, 3] : fa is equal to 1;
- p = [2, 3, 1] : fa is equal to 1;
- p = [3, 1, 2] : fa is equal to 0;
- p = [3, 2, 1] : fa is equal to 0.

Where p is the array of the indices of initial array a. The sum of fa is equal to 4.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
One day Igor K. stopped programming and took up math. One late autumn evening he was sitting at a table reading a book and thinking about something.

The following statement caught his attention: "Among any six people there are either three pairwise acquainted people or three pairwise unacquainted people"

Igor just couldn't get why the required minimum is 6 people. "Well, that's the same for five people, too!" — he kept on repeating in his mind. — "Let's take, say, Max, Ilya, Vova — here, they all know each other! And now let's add Dima and Oleg to Vova — none of them is acquainted with each other! Now, that math is just rubbish!"

Igor K. took 5 friends of his and wrote down who of them is friends with whom. Now he wants to check whether it is true for the five people that among them there are either three pairwise acquainted or three pairwise not acquainted people.

## Input Format
The first line contains an integer m (0 ≤ m ≤ 10), which is the number of relations of acquaintances among the five friends of Igor's.

Each of the following m lines contains two integers ai and bi (1 ≤ ai, bi ≤ 5;ai ≠ bi), where (ai, bi) is a pair of acquainted people. It is guaranteed that each pair of the acquaintances is described exactly once. The acquaintance relation is symmetrical, i.e. if x is acquainted with y, then y is also acquainted with x.

## Output Format
Print "FAIL", if among those five people there are no either three pairwise acquainted or three pairwise unacquainted people. Otherwise print "WIN".

## Examples
```input
4
1 3
2 3
1 4
5 3
```
```output
WIN
```
-----
```input
5
1 2
2 3
3 4
4 5
5 1
```
```output
FAIL
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Mikhail walks on a 2D plane. He can go either up or right. You are given a sequence of Mikhail's moves. He thinks that this sequence is too long and he wants to make it as short as possible.

In the given sequence moving up is described by character U and moving right is described by character R. Mikhail can replace any pair of consecutive moves RU or UR with a diagonal move (described as character D). After that, he can go on and do some other replacements, until there is no pair of consecutive moves RU or UR left.

Your problem is to print the minimum possible length of the sequence of moves after the replacements.

## Input Format
The first line of the input contains one integer n (1 ≤ n ≤ 100) — the length of the sequence. The second line contains the sequence consisting of n characters U and R.

## Output Format
Print the minimum possible length of the sequence of moves after all replacements are done.

## Examples
```input
5
RUURU
```
```output
3
```
-----
```input
17
UUURRRRRUUURURUUU
```
```output
13
```

## Note
In the first test the shortened sequence of moves may be DUD (its length is 3).

In the second test the shortened sequence of moves can be UUDRRRDUDDUUU (its length is 13).

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a string s consisting of n lowercase Latin letters. You have to type this string using your keyboard.

Initially, you have an empty string. Until you type the whole string, you may perform the following operation:

- add a character to the end of the string.

Besides, at most once you may perform one additional operation: copy the string and append it to itself.

For example, if you have to type string abcabca, you can type it in 7 operations if you type all the characters one by one. However, you can type it in 5 operations if you type the string abc first and then copy it and type the last character.

If you have to type string aaaaaaaaa, the best option is to type 4 characters one by one, then copy the string, and then type the remaining character.

Print the minimum number of operations you need to type the given string.

## Input Format
The first line of the input containing only one integer number n (1 ≤ n ≤ 100) — the length of the string you have to type. The second line containing the string s consisting of n lowercase Latin letters.

## Output Format
Print one integer number — the minimum number of operations you need to type the given string.

## Examples
```input
7
abcabca
```
```output
5
```
-----
```input
8
abcdefgh
```
```output
8
```

## Note
The first test described in the problem statement.

In the second test you can only type all the characters one by one.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.5 seconds
Memory limit: 256.0 MB

# Problem
Today you are going to lead a group of elven archers to defend the castle that is attacked by an army of angry orcs. Three sides of the castle are protected by impassable mountains and the remaining side is occupied by a long wall that is split into n sections. At this moment there are exactly ai archers located at the i-th section of this wall. You know that archer who stands at section i can shoot orcs that attack section located at distance not exceeding r, that is all such sections j that |i - j| ≤ r. In particular, r = 0 means that archers are only capable of shooting at orcs who attack section i.

Denote as defense level of section i the total number of archers who can shoot at the orcs attacking this section. Reliability of the defense plan is the minimum value of defense level of individual wall section.

There is a little time left till the attack so you can't redistribute archers that are already located at the wall. However, there is a reserve of k archers that you can distribute among wall sections in arbitrary way. You would like to achieve maximum possible reliability of the defence plan.

## Input Format
The first line of the input contains three integers n, r and k (1 ≤ n ≤ 500 000, 0 ≤ r ≤ n, 0 ≤ k ≤ 1018) — the number of sections of the wall, the maximum distance to other section archers can still shoot and the number of archers yet to be distributed along the wall. The second line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 109) — the current number of archers at each section.

## Output Format
Print one integer — the maximum possible value of defense plan reliability, i.e. the maximum possible value of minimum defense level if we distribute k additional archers optimally.

## Examples
```input
5 0 6
5 4 3 4 9
```
```output
5
```
-----
```input
4 2 0
1 2 3 4
```
```output
6
```
-----
```input
5 1 1
2 1 2 1 2
```
```output
3
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
To make a paper airplane, one has to use a rectangular piece of paper. From a sheet of standard size you can make $$$s$$$ airplanes.

A group of $$$k$$$ people decided to make $$$n$$$ airplanes each. They are going to buy several packs of paper, each of them containing $$$p$$$ sheets, and then distribute the sheets between the people. Each person should have enough sheets to make $$$n$$$ airplanes. How many packs should they buy?

## Input Format
The only line contains four integers $$$k$$$, $$$n$$$, $$$s$$$, $$$p$$$ ($$$1 \le k, n, s, p \le 10^4$$$) — the number of people, the number of airplanes each should make, the number of airplanes that can be made using one sheet and the number of sheets in one pack, respectively.

## Output Format
Print a single integer — the minimum number of packs they should buy.

## Examples
```input
5 3 2 3
```
```output
4
```
-----
```input
5 3 100 1
```
```output
5
```

## Note
In the first sample they have to buy $$$4$$$ packs of paper: there will be $$$12$$$ sheets in total, and giving $$$2$$$ sheets to each person is enough to suit everyone's needs.

In the second sample they have to buy a pack for each person as they can't share sheets.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.5 seconds
Memory limit: 256.0 MB

# Problem
Arkady is playing Battleship. The rules of this game aren't really important.

There is a field of $$$n \times n$$$ cells. There should be exactly one $$$k$$$-decker on the field, i. e. a ship that is $$$k$$$ cells long oriented either horizontally or vertically. However, Arkady doesn't know where it is located. For each cell Arkady knows if it is definitely empty or can contain a part of the ship.

Consider all possible locations of the ship. Find such a cell that belongs to the maximum possible number of different locations of the ship.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 100$$$) — the size of the field and the size of the ship.

The next $$$n$$$ lines contain the field. Each line contains $$$n$$$ characters, each of which is either '#' (denotes a definitely empty cell) or '.' (denotes a cell that can belong to the ship).

## Output Format
Output two integers — the row and the column of a cell that belongs to the maximum possible number of different locations of the ship.

If there are multiple answers, output any of them. In particular, if no ship can be placed on the field, you can output any cell.

## Examples
```input
4 3
#..#
#.#.
....
.###
```
```output
3 2
```
-----
```input
10 4
#....##...
.#...#....
..#..#..#.
...#.#....
.#..##.#..
.....#...#
...#.##...
.#...#.#..
.....#..#.
...#.#...#
```
```output
6 1
```
-----
```input
19 6
##..............###
#......#####.....##
.....#########.....
....###########....
...#############...
..###############..
.#################.
.#################.
.#################.
.#################.
#####....##....####
####............###
####............###
#####...####...####
.#####..####..#####
...###........###..
....###########....
.........##........
#.................#
```
```output
1 8
```

## Note
The picture below shows the three possible locations of the ship that contain the cell $$$(3, 2)$$$ in the first sample.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
$$$k$$$ people want to split $$$n$$$ candies between them. Each candy should be given to exactly one of them or be thrown away.

The people are numbered from $$$1$$$ to $$$k$$$, and Arkady is the first of them. To split the candies, Arkady will choose an integer $$$x$$$ and then give the first $$$x$$$ candies to himself, the next $$$x$$$ candies to the second person, the next $$$x$$$ candies to the third person and so on in a cycle. The leftover (the remainder that is not divisible by $$$x$$$) will be thrown away.

Arkady can't choose $$$x$$$ greater than $$$M$$$ as it is considered greedy. Also, he can't choose such a small $$$x$$$ that some person will receive candies more than $$$D$$$ times, as it is considered a slow splitting.

Please find what is the maximum number of candies Arkady can receive by choosing some valid $$$x$$$.

## Input Format
The only line contains four integers $$$n$$$, $$$k$$$, $$$M$$$ and $$$D$$$ ($$$2 \le n \le 10^{18}$$$, $$$2 \le k \le n$$$, $$$1 \le M \le n$$$, $$$1 \le D \le \min{(n, 1000)}$$$, $$$M \cdot D \cdot k \ge n$$$) — the number of candies, the number of people, the maximum number of candies given to a person at once, the maximum number of times a person can receive candies.

## Output Format
Print a single integer — the maximum possible number of candies Arkady can give to himself.

Note that it is always possible to choose some valid $$$x$$$.

## Examples
```input
20 4 5 2
```
```output
8
```
-----
```input
30 9 4 1
```
```output
4
```

## Note
In the first example Arkady should choose $$$x = 4$$$. He will give $$$4$$$ candies to himself, $$$4$$$ candies to the second person, $$$4$$$ candies to the third person, then $$$4$$$ candies to the fourth person and then again $$$4$$$ candies to himself. No person is given candies more than $$$2$$$ times, and Arkady receives $$$8$$$ candies in total.

Note that if Arkady chooses $$$x = 5$$$, he will receive only $$$5$$$ candies, and if he chooses $$$x = 3$$$, he will receive only $$$3 + 3 = 6$$$ candies as well as the second person, the third and the fourth persons will receive $$$3$$$ candies, and $$$2$$$ candies will be thrown away. He can't choose $$$x = 1$$$ nor $$$x = 2$$$ because in these cases he will receive candies more than $$$2$$$ times.

In the second example Arkady has to choose $$$x = 4$$$, because any smaller value leads to him receiving candies more than $$$1$$$ time.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You're given a row with $$$n$$$ chairs. We call a seating of people "maximal" if the two following conditions hold:

1. There are no neighbors adjacent to anyone seated.
2. It's impossible to seat one more person without violating the first rule.

The seating is given as a string consisting of zeros and ones ($$$0$$$ means that the corresponding seat is empty, $$$1$$$ — occupied). The goal is to determine whether this seating is "maximal".

Note that the first and last seats are not adjacent (if $$$n \ne 2$$$).

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 1000$$$) — the number of chairs.

The next line contains a string of $$$n$$$ characters, each of them is either zero or one, describing the seating.

## Output Format
Output "Yes" (without quotation marks) if the seating is "maximal". Otherwise print "No".

You are allowed to print letters in whatever case you'd like (uppercase or lowercase).

## Examples
```input
3
101
```
```output
Yes
```
-----
```input
4
1011
```
```output
No
```
-----
```input
5
10001
```
```output
No
```

## Note
In sample case one the given seating is maximal.

In sample case two the person at chair three has a neighbour to the right.

In sample case three it is possible to seat yet another person into chair three.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
For long time scientists study the behavior of sharks. Sharks, as many other species, alternate short movements in a certain location and long movements between locations.

Max is a young biologist. For $$$n$$$ days he watched a specific shark, and now he knows the distance the shark traveled in each of the days. All the distances are distinct. Max wants to know now how many locations the shark visited. He assumed there is such an integer $$$k$$$ that if the shark in some day traveled the distance strictly less than $$$k$$$, then it didn't change the location; otherwise, if in one day the shark traveled the distance greater than or equal to $$$k$$$; then it was changing a location in that day. Note that it is possible that the shark changed a location for several consecutive days, in each of them the shark traveled the distance at least $$$k$$$.

The shark never returned to the same location after it has moved from it. Thus, in the sequence of $$$n$$$ days we can find consecutive nonempty segments when the shark traveled the distance less than $$$k$$$ in each of the days: each such segment corresponds to one location. Max wants to choose such $$$k$$$ that the lengths of all such segments are equal.

Find such integer $$$k$$$, that the number of locations is as large as possible. If there are several such $$$k$$$, print the smallest one.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the number of days.

The second line contains $$$n$$$ distinct positive integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the distance traveled in each of the day.

## Output Format
Print a single integer $$$k$$$, such that

1. the shark was in each location the same number of days,
2. the number of locations is maximum possible satisfying the first condition,
3. $$$k$$$ is smallest possible satisfying the first and second conditions.

## Examples
```input
8
1 2 7 3 4 8 5 6
```
```output
7
```
-----
```input
6
25 1 2 3 14 36
```
```output
2
```

## Note
In the first example the shark travels inside a location on days $$$1$$$ and $$$2$$$ (first location), then on $$$4$$$-th and $$$5$$$-th days (second location), then on $$$7$$$-th and $$$8$$$-th days (third location). There are three locations in total.

In the second example the shark only moves inside a location on the $$$2$$$-nd day, so there is only one location.

Now solve the problem and return the code.