You discovered that the problems in the contest were shuffled, so you want to analyze their difficulty.
You assume that the difficulty of each of the $$$n$$$ problems is described by a permutation $$$p = (p_1, \cdots , p_n)$$$ (a permutation of length $$$n$$$ contains each of the numbers from $$$1$$$ to $$$n$$$ exactly once).
For each number $$$k$$$, you want to determine whether the $$$k$$$ easiest problems (numbered $$$1, \cdots , k$$$) appear in the permutation strictly earlier than the $$$k$$$ hardest problems (numbered $$$n, \cdots , n-k+1$$$).
Let the indices of the $$$k$$$ easiest problems be given by the set $$$A_k$$$, and the indices of the $$$k$$$ hardest problems by the set $$$B_k$$$.
Then, for a given number $$$k$$$, it is necessary to check that for any $$$a \in A_k, b \in B_k$$$, the inequality $$$a \lt b$$$ holds.
You need to find the maximum possible $$$k \ge 1$$$ for which the corresponding sets $$$A_k, B_k$$$ satisfy the condition above, or report that no such $$$k$$$ exists.
The first line contains an integer $$$n (1 \le n \le 10^5)$$$ — the number of problems in the contest.
The second line contains $$$n$$$ numbers $$$p_1, p_2, \ldots, p_n\, (1 \le p_i \le n)$$$ — a permutation describing the difficulty of the problems. It is guaranteed that each of the numbers from $$$1$$$ to $$$n$$$ appears exactly once.
In the only line, output the maximum possible $$$k \ge 1$$$ satisfying the condition of the problem.
If no such $$$k$$$ exists, output $$$-1$$$.
71 4 2 3 5 7 6
3
33 2 1
-1
As is well known, the Earth revolves around the Sun, while the Solar System itself moves through space, and so on.
$$$Andrew-13$$$ became interested in whether the sum of these movements could be exactly zero. Therefore, he asks you to solve the following problem:
It is known that the motion of some object is described by vectors $$$\vec{v_1}, \cdots ,\vec{v_n}$$$. You need to determine whether the sum of these vectors can be equal to the zero vector.
However, instead of the vectors themselves, you are only given their possible lengths (the directions of the vectors may be arbitrary). The lengths are given as segments, that is, vector number $$$i$$$ may have any length belonging to the segment $$$[l_i; r_i]$$$.
For a vector $$$\vec{v} = (x, y, z)$$$, its length is defined as $$$|\vec{v}| = \sqrt{x^2 + y^2 + z^2}$$$.
The first line of the input contains an integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of vectors.
The second line contains $$$n$$$ integers $$$l_1, l_2, \ldots, l_n\, (0\le l_i \le 10^9)$$$.
The next line contains $$$n$$$ integers $$$r_1, r_2, \ldots, r_n\, (l_i \le r_i \le 10^9)$$$.
If it is possible to choose directions for the vectors and choose some lengths from the segments $$$[l_i; r_i]$$$ so that their vector sum is equal to the zero vector, then output in a separate line their lengths $$$a_1, \cdots , a_n$$$ $$$(l_i \le a_i \le r_i)$$$ such that it is possible to choose suitable directions for them so that their sum is the zero vector.
Otherwise, output $$$-1$$$.
32 4 510 5 9
3 4 5
20 21 3
-1
Do you believe in alternative worlds? A group of researchers has discovered an anomaly that may indicate the existence of parallel realities. To confirm or refute the theory, they need to solve the following problem:
You are given a multiset $$$a$$$ consisting of numbers $$$a_1, \cdots, a_n$$$. It is required to split it into some collection of non-empty multisets $$$S_1, \cdots, S_k$$$ so as to maximize the sum of their medians.
In other words, you need to choose the number of multisets $$$k$$$ and assign each element of the multiset $$$a$$$ to exactly one of the sets $$$S_1, \cdots, S_k$$$. Then you need to compute $$$x = med(S_1) + med(S_2) + \cdots + med(S_k)$$$.
As the answer, you need to find the maximum possible value of $$$x$$$.
In this problem, for a sorted set $$$S$$$ with elements $$$s_1, \cdots, s_m$$$ (arranged in increasing order), the median is defined as follows: $$$med(S) = s_{\lceil \frac{n+1}{2} \rceil}$$$.
For example: $$$med(\{1, 5, 13\}) = 5$$$, $$$med(\{1, 5, 7, 13\}) = 7$$$.
The first line of the input contains the number $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$).
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n\, (|a_i| \le 10^9)$$$ — the values of the elements of the multiset $$$a$$$.
Print the answer to the problem in the only line.
2-190 -94
-94
530 -5 1 -1 -10
30
Do you believe in alternative worlds? A group of researchers has discovered an anomaly that may indicate the existence of parallel realities. To confirm or refute the theory, they need to solve the following problem:
You are given a multiset $$$a$$$ consisting of numbers $$$a_1, \cdots, a_n$$$. It is required to split it into some collection of non-empty multisets $$$S_1, \cdots, S_k$$$ so as to maximize the sum of their medians.
In other words, you need to choose the number of multisets $$$k$$$ and assign each element of the multiset $$$a$$$ to exactly one of the sets $$$S_1, \cdots, S_k$$$. Then you need to compute $$$x = med(S_1) + med(S_2) + \cdots + med(S_k)$$$.
As the answer, you need to find the maximum possible value of $$$x$$$.
In this problem, for a sorted set $$$S$$$ with elements $$$s_1, \cdots, s_m$$$ (arranged in increasing order), the median is defined as follows: $$$med(S) = (s_{\lceil \frac{n}{2} \rceil} + s_{\lceil \frac{n+1}{2} \rceil}) / 2$$$.
For example: $$$med(\{1, 5, 13\}) = 5$$$, $$$med(\{1, 5, 7, 13\}) = 6$$$.
The first line of the input contains the number $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$).
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n\, (|a_i| \le 10^9)$$$ — the values of the elements of the multiset $$$a$$$.
In the only line, print the answer to the problem, multiplied by $$$2$$$.
2-190 -94
-284
530 -5 1 -1 -10
54
After a long journey in search of ancient treasures, Oliver is ready to begin the final trial.
Oliver is in a system of underground rooms connected by tunnels. To avoid traps, each tunnel can be traversed in only one direction.
Initially, Oliver is in room $$$1$$$, and the treasure is in room $$$n$$$. However, it is completely dark everywhere, so to reach room $$$n$$$, he will use the $$$k$$$ portable lamps he has. When Oliver is in a room, he may either place a lamp there, if he still has at least 1 lamp with him (and the room is dark), or pick up a lamp from there (if he had previously placed it there). However, he may move through a tunnel $$$u \to v$$$, leaving his current room $$$u$$$, only if at least one of the rooms $$$u, v$$$ contains a lamp that illuminates the passage (an illuminated room illuminates all passages entering and leaving that room).
Each lamp is itself a valuable artifact for Oliver, so he wants to reach room $$$n$$$ and keep all lamps with him, rather than leaving them scattered throughout the labyrinth.
At the same time, Oliver can use the power of the lamps to illuminate larger areas. Initially, he has an array $$$c$$$ of special rooms, which contains only room $$$1$$$ (that is, $$$c = [1]$$$). If Oliver places at least one of his lamps in a room $$$x$$$ that belongs to the array $$$c$$$, then all rooms from the array $$$c$$$ become illuminated.
Moreover, every thirteenth time Oliver enters the same room $$$u$$$, if there is an edge from it to a room belonging to the array $$$c$$$, then this room $$$u$$$ is added to the array $$$c$$$.
Help Oliver determine whether he can reach the treasure under the given conditions.
The first line contains integers $$$n, m$$$, and $$$k$$$ ($$$1 \le k \le n \le 5 \cdot 10^3$$$, $$$0 \le m \le 10^4$$$) — the number of rooms, corridors, and lamps Oliver has with him, respectively.
Each of the next $$$m$$$ lines contains a pair of integers $$$u_i$$$, $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$), meaning that there is a directed tunnel from $$$u_i$$$ to $$$v_i$$$.
If Oliver can reach room $$$n$$$ and keep all lamps with him, print «Yes»; otherwise, print «No».
5 8 31 42 11 32 23 23 44 55 3
Yes
4 4 41 21 22 33 1
No
Thanos sort is one of the sorting algorithms that works in time linear in the length of the array.
The sorting algorithm is as follows:
1) If the array $$$a = (a_1, \cdots , a_n)$$$ is already sorted, then the process stops. An array is considered sorted if for every $$$i$$$ from $$$2$$$ to $$$n$$$, it holds that $$$a_{i-1} \le a_i$$$.
2) Otherwise, either the first $$$\lceil \frac{n}{2} \rceil$$$ elements of the array or the last $$$\lfloor \frac{n}{2} \rfloor$$$ elements are chosen uniformly at random. All of them are removed, and the algorithm proceeds to step 1.
For example, sorting the array $$$[10, 4, 5, 6, 8]$$$ may look as follows:
$$$[10, 4, 5, 6, 8]$$$ -> $$$[6, 8]$$$
Or:
$$$[10, 4, 5, 6, 8]$$$ -> $$$[10, 4, 5]$$$ -> $$$[10, 4]$$$ -> $$$[10]$$$
Since many elements may disappear during Thanos sort, for an array $$$a$$$, let $$$f(a)$$$ be the expected number of elements remaining in the final array.
You are given some array $$$a$$$.
You need to process the following queries:
$$$i, x$$$ – assign $$$a_i := x$$$.
After each query, you need to output $$$f(a)$$$ for the current array.
The first line contains two integers $$$n, q$$$ ($$$1 \le n, q \le 10^6$$$) – the length of the array and the number of queries, respectively.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n\, (0 \le a_i \le 10^9)$$$ – the initial values of the array $$$a$$$.
Each of the next $$$q$$$ lines contains a pair of integers $$$i, x$$$ ($$$1 \le i \le n, 0 \le x \le 10^9$$$) – the parameters of the next query.
After each query, output $$$f(a)$$$ modulo $$$998244353$$$ on a separate line.
5 810 4 5 6 81 55 03 32 114 73 125 174 13
499122178 1 1 748683266 748683266 2 499122179 5
After long research into an ancient cipher, you are sure that you are closer than ever to deciphering it.
However, to do this, you need to reconstruct an array $$$a$$$ of length $$$n$$$ that satisfies certain properties, or determine that no such array exists.
1) All elements of the array $$$a$$$ are distinct non-negative integers not exceeding $$$10^{18}$$$.
2) For each index $$$i$$$ from $$$1$$$ to $$$n$$$, you are given an index $$$j \ne i$$$ such that for any $$$k$$$ $$$(k \ne i, k \ne j)$$$, the following holds: $$$|a_k - a_i| \gt |a_i - a_j|$$$.
3) Among all arrays satisfying conditions $$$1$$$ and $$$2$$$, the array $$$a$$$ has the minimum possible value of its maximum element.
If there are multiple arrays satisfying conditions $$$1$$$, $$$2$$$, and $$$3$$$, you may output any of them.
The first line of the input contains an integer $$$n$$$ ($$$2 \le n \le 10^6$$$) — the length of the array $$$a$$$.
The second line contains $$$n$$$ integers $$$j_1, j_2, \ldots, j_n\, (1 \le j \le n)$$$ — the indices $$$j$$$ known to you for the corresponding $$$i$$$.
If there exists at least one array satisfying conditions $$$1$$$, $$$2$$$, and $$$3$$$, output its elements $$$a_1, a_2, \ldots, a_n$$$ separated by spaces on a separate line.
Otherwise, output $$$-1$$$.
54 1 5 1 3
2 0 5 3 6
42 3 4 2
-1