The employees of the laboratory are restoring an archive of experiment results. They know that the records in a correct archive must be arranged in nondecreasing order of values. However, due to a program error, one continuous fragment of the archive may have been saved in reverse order.
The archive is represented by an array $$$a$$$ of length $$$n$$$. In one operation, you can choose two indices $$$l$$$ and $$$r$$$ $$$(1 \le l \lt r \le n)$$$ and reverse the order of the elements of the subarray $$$a_l, a_{l+1}, \ldots, a_r$$$.
Determine whether it is possible to obtain a nondecreasing array by performing at most one operation. If it is possible and the array is not sorted yet, output the boundaries of a suitable subarray. If the array is already sorted, report it separately. If it is impossible to obtain a nondecreasing array, report that as well.
The first line of the input contains an integer $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ — the length of the array $$$a$$$.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — the values of the elements of the array $$$a$$$.
If the array $$$a$$$ is already nondecreasing, print the number $$$0$$$.
If it is impossible to obtain a nondecreasing array by performing at most one operation, print the number $$$-1$$$.
Otherwise, print the boundaries $$$l, r$$$ $$$(1 \le l \lt r \le n)$$$ of the subarray on which the operation described in the statement should be performed.
11
0
57 9 10 9 20
3 4
68 9 1 3 5 7
-1
A jeweler is assembling a necklace from multicolored beads and wants to slightly change its appearance.
There are $$$n$$$ beads on a string. The color of the $$$i$$$-th bead is given by an integer $$$a_i$$$. We will assume that the necklace is not cyclic, that is, the first and the last beads are not considered adjacent.
The jeweler must choose exactly one color $$$x$$$ and remove all beads of that color from the necklace. After that, the remaining beads shift while preserving their relative order. Before performing this operation, there must be at least one bead of color $$$x$$$ in the necklace.
It is necessary to determine the maximum number of consecutive beads of the same color that can be obtained after performing this operation.
The first line of the input contains one integer $$$n$$$ $$$(1 \le n \le 10^6)$$$ — the number of beads in the necklace.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \le a_i \le n)$$$ — the colors of the beads in the order they are arranged on the string.
Print one integer in a single line — the maximum number of consecutive beads of the same color that can be obtained after removing all beads of one chosen color.
31 1 1
0
71 2 1 3 1 1 2
3
A recently published book receives readers' ratings on a scale from $$$1$$$ to $$$n$$$. Readers leave reviews one by one, and at any moment the book's rating is the arithmetic mean of all ratings given so far.
For each reader, their type $$$t_i$$$ and desired rating $$$x_i$$$ are known.
If $$$t_i = \texttt{S}$$$, then the reader always gives the book rating $$$x_i$$$.
If $$$t_i = \texttt{D}$$$, then before voting the reader sees the current rating of the book and the number of readers who have already voted. Then they choose an integer rating from $$$1$$$ to $$$n$$$ so that the book's rating after their vote is as close as possible to $$$x_i$$$.
The organizers may choose any order in which the readers leave their reviews.
$$$\texttt{Andrew-13}$$$ became interested in the minimum and maximum possible final ratings of the book. Find these values.
The first line of the input contains 2 integers $$$n, m$$$ $$$(1 \le n, m \le 2 \cdot 10^5)$$$ — the maximum possible rating of the book and the number of readers, respectively.
Each of the next $$$m$$$ lines contains a character $$$t_i$$$ ($$$t_i = \texttt{S}$$$ or $$$t_i = \texttt{D}$$$) and an integer $$$x_i$$$ $$$(1 \le x_i \le n)$$$ — the reader type and their desired rating.
The character $$$t_i$$$ is $$$\texttt{S}$$$ if the reader always gives rating $$$x_i$$$, or $$$\texttt{D}$$$ if the reader chooses a rating so that the final rating after their vote is as close as possible to $$$x_i$$$.
Print two numbers in a single line — the minimum and maximum possible final ratings of the book.
Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-9}$$$.
Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is considered correct if $$$\frac{|a - b|}{\max(1, |b|)} \le 10^{-9}$$$.
10 3S 3S 5D 8
5.3333333333333 6.0000000000000
1000 4D 999D 101S 323D 812
487.0000000000000 606.0000000000000
There are $$$n$$$ collectible cards arranged in a fixed order on a strip. The $$$i$$$-th card has type number $$$a_i$$$.
The strip can be cut between some adjacent cards, obtaining several non-empty sets. The order of the cards cannot be changed, so each set consists of some contiguous fragment of the strip.
For a set of cards, define its $$$\operatorname{MEX}$$$ as the minimum non-negative type number that does not appear among the cards in that set. For example, $$$\operatorname{MEX}([0, 3, 2, 2, 0]) = 1$$$, and $$$\operatorname{MEX}([1, 2, 6]) = 0$$$.
A set is called $$$\texttt{valid}$$$ if its $$$\operatorname{MEX}$$$ lies in the range from $$$L$$$ to $$$R$$$ inclusive.
Find the number of ways to cut the strip so that all resulting sets are $$$\texttt{valid}$$$. Since the answer may be large, output it modulo $$$998244353$$$.
The first line of the input contains three integers $$$n$$$, $$$L$$$, and $$$R$$$ $$$(1 \le n \le 5 \cdot 10^5,\ 0 \le L \le R \le n)$$$ — the number of cards and the bounds of the valid values of $$$\operatorname{MEX}$$$.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(0 \le a_i \le n)$$$ — the type numbers of the cards on the strip.
Print one number in a single line — the number of ways to cut the strip modulo $$$998244353$$$.
5 1 30 3 1 2 0
2
6 0 20 1 0 2 3 0
24
A student is preparing for an olympiad and plans to solve $$$n$$$ problems. The difficulty of the $$$i$$$-th problem is $$$a_i$$$.
Before the preparation starts, the problems are randomly shuffled, and then the student solves them in the resulting order. Each of the $$$n!$$$ permutations of the problems is equally likely. Initially, the student remembers the solutions to none of the problems.
For each problem $$$i$$$, the number $$$x_i$$$ is also known — the probability of forgetting the solution to the problem, in percent. Then $$$p_i = x_i / 100$$$ is the probability of forgetting the solution to the $$$i$$$-th problem.
When solving the next problem $$$i$$$, the student performs the following actions:
— Solves problem $$$i$$$ and remembers its solution.
— Gains $$$1$$$ unit of experience for each problem $$$j$$$ whose solution he remembers and for which $$$a_j \le a_i$$$.
— For each problem $$$j \ne i$$$ whose solution he remembers, with probability $$$p_j$$$ he forgets its solution. All such events are independent.
Thus, the student cannot forget the solution to a problem immediately after solving it. However, after solving each subsequent problem, he may forget it with the corresponding probability for that problem. If the solution to a problem is forgotten, then the student will not remember it again until the end of the preparation.
Find the expected amount of experience gained.
The first line of the input contains a single integer $$$n$$$ $$$(1 \le n \le 3 \cdot 10^5)$$$ — the number of problems.
Each of the next $$$n$$$ lines contains two integers $$$a_i$$$ and $$$x_i$$$ $$$(1 \le a_i \le 10^9,\ 0 \le x_i \le 100)$$$ — the difficulty of the $$$i$$$-th problem and the number specifying the probability of forgetting its solution in percent.
The values $$$a_i$$$ are not necessarily distinct.
It can be shown that the expected amount of experience can be represented as an irreducible fraction $$$\frac{p}{q}$$$, where $$$q$$$ is not divisible by $$$998244353$$$.
In the only line, output one number — the value of $$$p \cdot q^{-1}$$$ modulo $$$998244353$$$, where $$$q^{-1}$$$ is the multiplicative inverse of $$$q$$$ modulo $$$998244353$$$.
33 506 1001 0
915057328
51 231 782 452 893 100
154133329
This is the easy version of the problem. The difference between the versions is that in this version you need to finish the path in the starting cave.
Henry went on an expedition into a network of caves in search of ancient artifacts. The entrance to the caves is at vertex $$$1$$$, and the corridors between the caves form a tree.
Henry lights his way with a magic lamp. To pass through the $$$i$$$-th corridor, the lamp spends $$$w_i$$$ units of charge each time it is traversed.
However, the cave corridors are extremely unstable. After being traversed twice, a corridor becomes too fragile, and it is impossible to use it a third time. Therefore, Henry can traverse each corridor at most twice, regardless of the direction of movement.
There is an artifact in every cave. On the first visit to vertex $$$v$$$, the artifact changes the lamp charge by $$$a_v$$$ units: some artifacts restore charge (those with $$$a_v \gt 0$$$), while others are cursed and, on the contrary, take it away ($$$a_v \lt 0$$$). Visiting the cave again has no effect on the lamp charge.
At the beginning of the expedition, Henry is in cave $$$1$$$ and immediately activates the artifact located there. The lamp charge must never become negative at any moment.
Henry must visit all caves and collect all artifacts. After that, he must return to cave $$$1$$$ and leave the dungeon.
Determine the minimum initial lamp charge with which Henry can complete the expedition.
The first line of the input contains one integer $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ — the number of caves.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(-10^9 \le a_i \le 10^9)$$$ — the changes in lamp charge after the first visit to the corresponding caves. Note that each corridor can be traversed at most twice, regardless of direction.
The next $$$n - 1$$$ lines contain three integers each: $$$u_i$$$, $$$v_i$$$, and $$$w_i$$$ $$$(1 \le u_i, v_i \le n,\ u_i \ne v_i,\ 1 \le w_i \le 10^9)$$$ — the endpoints of the $$$i$$$-th corridor and the amount of charge required to traverse it.
It is guaranteed that the corridors form a tree.
In a single line, print one integer — the minimum initial lamp charge with which Henry can visit all caves without ever letting the lamp charge become negative.
51 10 -2 6 71 2 101 3 23 4 13 5 7
18
42 -90 15 301 2 42 3 51 4 10
87
This is the hard version of the problem. The difference between the versions is that in this version, the path may end in any cave.
Henry went on an expedition into a network of caves in search of ancient artifacts. The entrance to the caves is at vertex $$$1$$$, and the corridors between caves form a tree.
Henry lights his way with a magic lamp. To pass through the $$$i$$$-th corridor, the lamp spends $$$w_i$$$ units of charge each time it is traversed.
However, the cave corridors are extremely unstable. After two traversals of the same corridor, its vault becomes too fragile, and it is impossible to use this corridor a third time. Therefore, Henry may traverse each corridor at most twice, regardless of the direction of movement.
There is an artifact in every cave. On the first visit to vertex $$$v$$$, the artifact changes the lamp charge by $$$a_v$$$ units: some artifacts restore charge (those with $$$a_v \gt 0$$$), while others are cursed and instead take it away ($$$a_v \lt 0$$$). Visiting the cave again has no effect on the lamp charge.
At the beginning of the expedition, Henry is in cave $$$1$$$ and immediately activates the artifact there. The lamp charge must never become negative at any moment.
Henry must visit all caves and collect all artifacts. After that, he can activate a portal in any cave and leave the dungeon, so he does not need to return to the entrance.
Determine the minimum initial lamp charge with which Henry can complete the expedition.
The first line contains one integer $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ — the number of caves.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(-10^9 \le a_i \le 10^9)$$$ — the changes in lamp charge after the first visit to the corresponding caves. Note that each corridor can be traversed at most twice, regardless of direction.
The next $$$n - 1$$$ lines contain three integers each: $$$u_i$$$, $$$v_i$$$, and $$$w_i$$$ $$$(1 \le u_i, v_i \le n,\ u_i \ne v_i,\ 1 \le w_i \le 10^9)$$$ — the endpoints of the $$$i$$$-th corridor and the amount of charge required to traverse it.
It is guaranteed that the corridors form a tree.
Print one integer — the minimum initial lamp charge with which Henry can visit all caves without the lamp charge ever becoming negative.
51 10 -2 6 71 2 101 3 23 4 13 5 7
16
42 -90 15 301 2 42 3 51 4 10
87