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 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
The three friends, Kuro, Shiro, and Katie, met up again! It's time for a party...

What the cats do when they unite? Right, they have a party. Since they wanted to have as much fun as possible, they invited all their friends. Now $$$n$$$ cats are at the party, sitting in a circle and eating soup. The rules are simple: anyone having finished their soup leaves the circle.

Katie suddenly notices that whenever a cat leaves, the place where she was sitting becomes an empty space, which means the circle is divided into smaller continuous groups of cats sitting next to each other. At the moment Katie observes, there are $$$m$$$ cats who left the circle. This raises a question for Katie: what is the maximum possible number of groups the circle is divided into at the moment?

Could you help her with this curiosity?

You can see the examples and their descriptions with pictures in the "Note" section.

## Input Format
The only line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 1000$$$, $$$0 \leq m \leq n$$$) — the initial number of cats at the party and the number of cats who left the circle at the moment Katie observes, respectively.

## Output Format
Print a single integer — the maximum number of groups of cats at the moment Katie observes.

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

## Note
In the first example, originally there are $$$7$$$ cats sitting as shown below, creating a single group:

At the observed moment, $$$4$$$ cats have left the table. Suppose the cats $$$2$$$, $$$3$$$, $$$5$$$ and $$$7$$$ have left, then there are $$$3$$$ groups remaining. It is possible to show that it is the maximum possible number of groups remaining.

In the second example, there are $$$6$$$ cats sitting as shown below:

At the observed moment, $$$2$$$ cats have left the table. Suppose the cats numbered $$$3$$$ and $$$6$$$ left, then there will be $$$2$$$ groups remaining ($$$\{1, 2\}$$$ and $$$\{4, 5\}$$$). It is impossible to have more than $$$2$$$ groups of cats remaining.

In the third example, no cats have left, so there is $$$1$$$ group consisting of all cats.

In the fourth example, all cats have left the circle, so there are $$$0$$$ groups.

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
This problem is same as the next one, but has smaller constraints.

Shiro's just moved to the new house. She wants to invite all friends of her to the house so they can play monopoly. However, her house is too small, so she can only invite one friend at a time.

For each of the $$$n$$$ days since the day Shiro moved to the new house, there will be exactly one cat coming to the Shiro's house. The cat coming in the $$$i$$$-th day has a ribbon with color $$$u_i$$$. Shiro wants to know the largest number $$$x$$$, such that if we consider the streak of the first $$$x$$$ days, it is possible to remove exactly one day from this streak so that every ribbon color that has appeared among the remaining $$$x - 1$$$ will have the same number of occurrences.

For example, consider the following sequence of $$$u_i$$$: $$$[2, 2, 1, 1, 5, 4, 4, 5]$$$. Then $$$x = 7$$$ makes a streak, since if we remove the leftmost $$$u_i = 5$$$, each ribbon color will appear exactly twice in the prefix of $$$x - 1$$$ days. Note that $$$x = 8$$$ doesn't form a streak, since you must remove exactly one day.

Since Shiro is just a cat, she is not very good at counting and needs your help finding the longest streak.

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

The second line contains $$$n$$$ integers $$$u_1, u_2, \ldots, u_n$$$ ($$$1 \leq u_i \leq 10$$$) — the colors of the ribbons the cats wear.

## Output Format
Print a single integer $$$x$$$ — the largest possible streak of days.

## Examples
```input
13
1 1 1 2 2 2 3 3 3 4 4 4 5
```
```output
13
```
-----
```input
5
10 2 5 4 1
```
```output
5
```
-----
```input
1
10
```
```output
1
```
-----
```input
7
3 2 1 1 4 5 1
```
```output
6
```
-----
```input
6
1 1 1 2 2 2
```
```output
5
```

## Note
In the first example, we can choose the longest streak of $$$13$$$ days, since upon removing the last day out of the streak, all of the remaining colors $$$1$$$, $$$2$$$, $$$3$$$, and $$$4$$$ will have the same number of occurrences of $$$3$$$. Note that the streak can also be $$$10$$$ days (by removing the $$$10$$$-th day from this streak) but we are interested in the longest streak.

In the fourth example, if we take the streak of the first $$$6$$$ days, we can remove the third day from this streak then all of the remaining colors $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$ and $$$5$$$ will occur exactly once.

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
This problem is same as the previous one, but has larger constraints.

Shiro's just moved to the new house. She wants to invite all friends of her to the house so they can play monopoly. However, her house is too small, so she can only invite one friend at a time.

For each of the $$$n$$$ days since the day Shiro moved to the new house, there will be exactly one cat coming to the Shiro's house. The cat coming in the $$$i$$$-th day has a ribbon with color $$$u_i$$$. Shiro wants to know the largest number $$$x$$$, such that if we consider the streak of the first $$$x$$$ days, it is possible to remove exactly one day from this streak so that every ribbon color that has appeared among the remaining $$$x - 1$$$ will have the same number of occurrences.

For example, consider the following sequence of $$$u_i$$$: $$$[2, 2, 1, 1, 5, 4, 4, 5]$$$. Then $$$x = 7$$$ makes a streak, since if we remove the leftmost $$$u_i = 5$$$, each ribbon color will appear exactly twice in the prefix of $$$x - 1$$$ days. Note that $$$x = 8$$$ doesn't form a streak, since you must remove exactly one day.

Since Shiro is just a cat, she is not very good at counting and needs your help finding the longest streak.

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

The second line contains $$$n$$$ integers $$$u_1, u_2, \ldots, u_n$$$ ($$$1 \leq u_i \leq 10^5$$$) — the colors of the ribbons the cats wear.

## Output Format
Print a single integer $$$x$$$ — the largest possible streak of days.

## Examples
```input
13
1 1 1 2 2 2 3 3 3 4 4 4 5
```
```output
13
```
-----
```input
5
10 100 20 200 1
```
```output
5
```
-----
```input
1
100000
```
```output
1
```
-----
```input
7
3 2 1 1 4 5 1
```
```output
6
```
-----
```input
6
1 1 1 2 2 2
```
```output
5
```

## Note
In the first example, we can choose the longest streak of $$$13$$$ days, since upon removing the last day out of the streak, all of the remaining colors $$$1$$$, $$$2$$$, $$$3$$$, and $$$4$$$ will have the same number of occurrences of $$$3$$$. Note that the streak can also be $$$10$$$ days (by removing the $$$10$$$-th day from this streak) but we are interested in the longest streak.

In the fourth example, if we take the streak of the first $$$6$$$ days, we can remove the third day from this streak then all of the remaining colors $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$ and $$$5$$$ will occur exactly once.

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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
During a normal walk in the forest, Katie has stumbled upon a mysterious code! However, the mysterious code had some characters unreadable. She has written down this code as a string $$$c$$$ consisting of lowercase English characters and asterisks ("*"), where each of the asterisks denotes an unreadable character. Excited with her discovery, Katie has decided to recover the unreadable characters by replacing each asterisk with arbitrary lowercase English letter (different asterisks might be replaced with different letters).

Katie has a favorite string $$$s$$$ and a not-so-favorite string $$$t$$$ and she would love to recover the mysterious code so that it has as many occurrences of $$$s$$$ as possible and as little occurrences of $$$t$$$ as possible. Formally, let's denote $$$f(x, y)$$$ as the number of occurrences of $$$y$$$ in $$$x$$$ (for example, $$$f(aababa, ab) = 2$$$). Katie wants to recover the code $$$c'$$$ conforming to the original $$$c$$$, such that $$$f(c', s) - f(c', t)$$$ is largest possible. However, Katie is not very good at recovering codes in general, so she would like you to help her out.

## Input Format
The first line contains string $$$c$$$ ($$$1 \leq |c| \leq 1000$$$) — the mysterious code . It is guaranteed that $$$c$$$ consists of lowercase English characters and asterisks "*" only.

The second and third line contain strings $$$s$$$ and $$$t$$$ respectively ($$$1 \leq |s|, |t| \leq 50$$$, $$$s \neq t$$$). It is guaranteed that $$$s$$$ and $$$t$$$ consist of lowercase English characters only.

## Output Format
Print a single integer — the largest possible value of $$$f(c', s) - f(c', t)$$$ of the recovered code.

## Examples
```input
*****
katie
shiro
```
```output
1
```
-----
```input
caat
caat
a
```
```output
-1
```
-----
```input
*a*
bba
b
```
```output
0
```
-----
```input
***
cc
z
```
```output
2
```

## Note
In the first example, for $$$c'$$$ equal to "katie" $$$f(c', s) = 1$$$ and $$$f(c', t) = 0$$$, which makes $$$f(c', s) - f(c', t) = 1$$$ which is the largest possible.

In the second example, the only $$$c'$$$ conforming to the given $$$c$$$ is "caat". The corresponding $$$f(c', s) - f(c', t) = 1 - 2 = -1$$$.

In the third example, there are multiple ways to recover the code such that $$$f(c', s) - f(c', t)$$$ is largest possible, for example "aaa", "aac", or even "zaz". The value of $$$f(c', s) - f(c', t) = 0$$$ for all of these recovered codes.

In the fourth example, the optimal recovered code $$$c'$$$ would be "ccc". The corresponding $$$f(c', s) - f(c', t) = 2$$$.

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
A telephone number is a sequence of exactly 11 digits, where the first digit is 8. For example, the sequence 80011223388 is a telephone number, but the sequences 70011223388 and 80000011223388 are not.

You are given a string $$$s$$$ of length $$$n$$$, consisting of digits.

In one operation you can delete any character from string $$$s$$$. For example, it is possible to obtain strings 112, 111 or 121 from string 1121.

You need to determine whether there is such a sequence of operations (possibly empty), after which the string $$$s$$$ becomes a telephone number.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 100$$$) — the length of string $$$s$$$.

The second line of each test case contains the string $$$s$$$ ($$$|s| = n$$$) consisting of digits.

## Output Format
For each test print one line.

If there is a sequence of operations, after which $$$s$$$ becomes a telephone number, print YES.

Otherwise, print NO.

## Examples
```input
2
13
7818005553535
11
31415926535
```
```output
YES
NO
```

## Note
In the first test case you need to delete the first and the third digits. Then the string 7818005553535 becomes 88005553535.

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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
A string is called bracket sequence if it does not contain any characters other than "(" and ")". A bracket sequence is called regular (shortly, RBS) if it is possible to obtain correct arithmetic expression by inserting characters "+" and "1" into this sequence. For example, "", "(())" and "()()" are RBS and ")(" and "(()" are not.

We can see that each opening bracket in RBS is paired with some closing bracket, and, using this fact, we can define nesting depth of the RBS as maximum number of bracket pairs, such that the $$$2$$$-nd pair lies inside the $$$1$$$-st one, the $$$3$$$-rd one — inside the $$$2$$$-nd one and so on. For example, nesting depth of "" is $$$0$$$, "()()()" is $$$1$$$ and "()((())())" is $$$3$$$.

Now, you are given RBS $$$s$$$ of even length $$$n$$$. You should color each bracket of $$$s$$$ into one of two colors: red or blue. Bracket sequence $$$r$$$, consisting only of red brackets, should be RBS, and bracket sequence, consisting only of blue brackets $$$b$$$, should be RBS. Any of them can be empty. You are not allowed to reorder characters in $$$s$$$, $$$r$$$ or $$$b$$$. No brackets can be left uncolored.

Among all possible variants you should choose one that minimizes maximum of $$$r$$$'s and $$$b$$$'s nesting depth. If there are multiple solutions you can print any of them.

## Input Format
The first line contains an even integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the length of RBS $$$s$$$.

The second line contains regular bracket sequence $$$s$$$ ($$$|s| = n$$$, $$$s_i \in \{$$$"(", ")"$$$\}$$$).

## Output Format
Print single string $$$t$$$ of length $$$n$$$ consisting of "0"-s and "1"-s. If $$$t_i$$$ is equal to 0 then character $$$s_i$$$ belongs to RBS $$$r$$$, otherwise $$$s_i$$$ belongs to $$$b$$$.

## Examples
```input
2
()
```
```output
11
```
-----
```input
4
(())
```
```output
0101
```
-----
```input
10
((()())())
```
```output
0110001111
```

## Note
In the first example one of optimal solutions is $$$s = $$$ "$$$\color{blue}{()}$$$". $$$r$$$ is empty and $$$b = $$$ "$$$()$$$". The answer is $$$\max(0, 1) = 1$$$.

In the second example it's optimal to make $$$s = $$$ "$$$\color{red}{(}\color{blue}{(}\color{red}{)}\color{blue}{)}$$$". $$$r = b = $$$ "$$$()$$$" and the answer is $$$1$$$.

In the third example we can make $$$s = $$$ "$$$\color{red}{(}\color{blue}{((}\color{red}{)()}\color{blue}{)())}$$$". $$$r = $$$ "$$$()()$$$" and $$$b = $$$ "$$$(()())$$$" and the answer is $$$2$$$.

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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array consisting of $$$n$$$ integers $$$a_1, a_2, \dots , a_n$$$ and an integer $$$x$$$. It is guaranteed that for every $$$i$$$, $$$1 \le a_i \le x$$$.

Let's denote a function $$$f(l, r)$$$ which erases all values such that $$$l \le a_i \le r$$$ from the array $$$a$$$ and returns the resulting array. For example, if $$$a = [4, 1, 1, 4, 5, 2, 4, 3]$$$, then $$$f(2, 4) = [1, 1, 5]$$$.

Your task is to calculate the number of pairs $$$(l, r)$$$ such that $$$1 \le l \le r \le x$$$ and $$$f(l, r)$$$ is sorted in non-descending order. Note that the empty array is also considered sorted.

## Input Format
The first line contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le n, x \le 10^6$$$) — the length of array $$$a$$$ and the upper limit for its elements, respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots a_n$$$ ($$$1 \le a_i \le x$$$).

## Output Format
Print the number of pairs $$$1 \le l \le r \le x$$$ such that $$$f(l, r)$$$ is sorted in non-descending order.

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

## Note
In the first test case correct pairs are $$$(1, 1)$$$, $$$(1, 2)$$$, $$$(1, 3)$$$ and $$$(2, 3)$$$.

In the second test case correct pairs are $$$(1, 3)$$$, $$$(1, 4)$$$, $$$(2, 3)$$$, $$$(2, 4)$$$, $$$(3, 3)$$$ and $$$(3, 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array $$$a_1, a_2, \dots, a_n$$$. All $$$a_i$$$ are pairwise distinct.

Let's define function $$$f(l, r)$$$ as follows:

- let's define array $$$b_1, b_2, \dots, b_{r - l + 1}$$$, where $$$b_i = a_{l - 1 + i}$$$;
- sort array $$$b$$$ in increasing order;
- result of the function $$$f(l, r)$$$ is $$$\sum\limits_{i = 1}^{r - l + 1}{b_i \cdot i}$$$.

Calculate $$$\left(\sum\limits_{1 \le l \le r \le n}{f(l, r)}\right) \mod (10^9+7)$$$, i.e. total sum of $$$f$$$ for all subsegments of $$$a$$$ modulo $$$10^9+7$$$.

## Input Format
The first line contains one integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — the length of array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$, $$$a_i \neq a_j$$$ for $$$i \neq j$$$) — array $$$a$$$.

## Output Format
Print one integer — the total sum of $$$f$$$ for all subsegments of $$$a$$$ modulo $$$10^9+7$$$

## Examples
```input
4
5 2 4 7
```
```output
167
```
-----
```input
3
123456789 214365879 987654321
```
```output
582491518
```

## Note
Description of the first example:

- $$$f(1, 1) = 5 \cdot 1 = 5$$$;
- $$$f(1, 2) = 2 \cdot 1 + 5 \cdot 2 = 12$$$;
- $$$f(1, 3) = 2 \cdot 1 + 4 \cdot 2 + 5 \cdot 3 = 25$$$;
- $$$f(1, 4) = 2 \cdot 1 + 4 \cdot 2 + 5 \cdot 3 + 7 \cdot 4 = 53$$$;
- $$$f(2, 2) = 2 \cdot 1 = 2$$$;
- $$$f(2, 3) = 2 \cdot 1 + 4 \cdot 2 = 10$$$;
- $$$f(2, 4) = 2 \cdot 1 + 4 \cdot 2 + 7 \cdot 3 = 31$$$;
- $$$f(3, 3) = 4 \cdot 1 = 4$$$;
- $$$f(3, 4) = 4 \cdot 1 + 7 \cdot 2 = 18$$$;
- $$$f(4, 4) = 7 \cdot 1 = 7$$$;

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
Alice and Bob have received three big piles of candies as a gift. Now they want to divide these candies as fair as possible. To do this, Alice takes one pile of candies, then Bob takes one of the other two piles. The last pile is split between Alice and Bob as they want: for example, it is possible that Alice takes the whole pile, and Bob gets nothing from it.

After taking the candies from the piles, if Alice has more candies than Bob, she discards some candies so that the number of candies she has is equal to the number of candies Bob has. Of course, Bob does the same if he has more candies.

Alice and Bob want to have as many candies as possible, and they plan the process of dividing candies accordingly. Please calculate the maximum number of candies Alice can have after this division process (of course, Bob will have the same number of candies).

You have to answer $$$q$$$ independent queries.

Let's see the following example: $$$[1, 3, 4]$$$. Then Alice can choose the third pile, Bob can take the second pile, and then the only candy from the first pile goes to Bob — then Alice has $$$4$$$ candies, and Bob has $$$4$$$ candies.

Another example is $$$[1, 10, 100]$$$. Then Alice can choose the second pile, Bob can choose the first pile, and candies from the third pile can be divided in such a way that Bob takes $$$54$$$ candies, and Alice takes $$$46$$$ candies. Now Bob has $$$55$$$ candies, and Alice has $$$56$$$ candies, so she has to discard one candy — and after that, she has $$$55$$$ candies too.

## Input Format
The first line of the input contains one integer $$$q$$$ ($$$1 \le q \le 1000$$$) — the number of queries. Then $$$q$$$ queries follow.

The only line of the query contains three integers $$$a, b$$$ and $$$c$$$ ($$$1 \le a, b, c \le 10^{16}$$$) — the number of candies in the first, second and third piles correspondingly.

## Output Format
Print $$$q$$$ lines. The $$$i$$$-th line should contain the answer for the $$$i$$$-th query — the maximum number of candies Alice can have after the division, if both Alice and Bob act optimally (of course, Bob will have the same number of candies).

## Examples
```input
4
1 3 4
1 10 100
10000000000000000 10000000000000000 10000000000000000
23 34 45
```
```output
4
55
15000000000000000
51
```

Now solve the problem and return the code.