Starting from $$$x$$$, what values can you reach?

Each operation replaces $$$x$$$ with $$$x / z$$$ where $$$z$$$ divides $$$x$$$.
So in a single step you can jump directly to any divisor of the current $$$x$$$.

Over multiple steps you can still only ever reach divisors of the original $$$x$$$.

To reach any divisor $$$d$$$ of $$$x$$$, just pick $$$z = x / d$$$ in one step — done.

Answer: YES if and only if $$$y$$$ divides $$$x$$$.

What does $$$n \times 11$$$ look like for a single-digit $$$n$$$?

$$$1 \times 11 = 11$$$, $$$\; 2 \times 11 = 22$$$, $$$\; 9 \times 11 = 99$$$.
It's always the digit repeated — i.e. $$$n$$$ concatenated with itself.

For $$$n$$$ with $$$d$$$ digits, we want $$$z$$$ such that $$$n \times z = \overline{nn}$$$ (n concatenated with n).

Note that $$$\overline{nn} = n \times 10^d + n = n \times (10^d + 1)$$$.

So $$$z = 10^d + 1$$$, where $$$d$$$ = number of digits in $$$n$$$.

For $$$n = 12$$$: $$$d = 2$$$, $$$z = 101$$$, $$$12 \times 101 = 1212$$$.
For $$$n = 123$$$: $$$d = 3$$$, $$$z = 1001$$$, $$$123 \times 1001 = 123123$$$.

The answer is almost always 1. Only a very specific type of string gives 2.

If the string starts and ends with the same character (e.g., both '0'), pick any "0[1...]0" substring — it is a palindrome — and delete one '1' from it at a time until the '1'-block disappears. Repeat for each '1'-block. The remaining '0's collapse to a single '0'. Answer 1.

Example:
01111101111011110
→ 001111011110
→ 00011110
→ 0000
→ 0

What if the first and last characters differ? E.g., starts '0', ends '1'.

Find any "1[...]1" substring (two '1's with characters between them) — "101" is a palindrome, for example. Delete the rightmost '1' from it, making the string end with '0'. Now first and last are both '0' — back to Hint 2. Answer still 1.

E.g., "0101": choose "101" (palindrome) → delete the last '1' → "010" → starts and ends with '0'. Answer 1.

The only stuck case: the string is sorted into exactly two blocks — all of one character followed by all of another (like "0000111111").

There is no '0' after the '1'-block, so no "0[1...]0" palindrome can be formed — the '1'-block can never be removed. At best each block compresses to one character, leaving "01". Answer 2.

Any operation on $$$[l, r]$$$ decomposes into non-overlapping length-2 blocks plus at most one length-1 at the end:
$$$[l, r] = [l, l+1] + [l+2, l+3] + \cdots$$$ (and $$$[r, r]$$$ if the length is odd).

So, we should just use following 2 operations:
Length-2: $$$[i, i+1]$$$ — adds $$$+1$$$ to $$$a_i$$$, $$$-1$$$ to $$$a_{i+1}$$$.
Length-1: $$$[i, i]$$$ — adds $$$+1$$$ to $$$a_i$$$.

Greedy: fix positions left to right.

For $$$i = 0$$$ to $$$n-2$$$: apply $$$[i, i+1]$$$ repeatedly until $$$a_i = b_i$$$ (increases $$$a_i$$$, borrows from $$$a_{i+1}$$$).
For $$$i = n-1$$$: apply $$$[n-1, n-1]$$$ repeatedly until $$$a_{n-1} = b_{n-1}$$$.

Answer is NO if at any step $$$i$$$, after $$$a_0 \ldots a_{i-1}$$$ have been made equal to $$$b_0 \ldots b_{i-1}$$$, the current value of $$$a_i \gt b_i$$$.

Let $$$P(u)$$$ = product of node values on the path from the root to $$$u$$$ (inclusive).

Then the product of values along any path $$$u \to v$$$ is:

$$$P(\text{lca})^2$$$ is always a perfect square, so dividing by it does not affect whether the result is a perfect square.

Thus $$$\text{prod}(u, \ldots, v)$$$ is a perfect square iff $$$P(u) \cdot P(v) \cdot a[\text{lca}(u,v)]$$$ is a perfect square.

Expand $$$\text{prod}(u,v) \cdot \text{prod}(v,w) \cdot \text{prod}(w,u)$$$ using the formula from Hint 1:

All $$$P^2$$$ terms are perfect squares and can be ignored. The triple is good iff $$$a[\text{lca}(u,v)] \cdot a[\text{lca}(v,w)] \cdot a[\text{lca}(w,u)]$$$ is a perfect square.

The three pairwise LCAs $$$\text{lca}(u,v)$$$, $$$\text{lca}(u,w)$$$, $$$\text{lca}(v,w)$$$ cannot all be distinct — at most 2 distinct values appear among them (hint: Auxiliary Tree).

So the product $$$a[\text{lca}(u,v)] \cdot a[\text{lca}(u,w)] \cdot a[\text{lca}(v,w)]$$$ always equals some $$$a[m]^2 \cdot a[m']$$$ (one node repeated, one appearing once) or $$$a[m]^3$$$ (all three equal). Either way, it is a perfect square iff the non-repeated node $$$m$$$ has a perfect square value.

The meeting point of a triple $$$(u, v, w)$$$ is the unique node that lies on all three pairwise paths. It is the non-repeated LCA from Hint 5.

For each node $$$m$$$ with $$$a[m]$$$ a perfect square, count triples $$$(u, v, w)$$$ where $$$m$$$ is the meeting point.

$$$m$$$ is the meeting point iff $$$u, v, w$$$ each lie in a different branch of $$$m$$$. Branches = $$$m$$$ itself (size $$$1$$$), the rest-of-tree above $$$m$$$ (size $$$n - \text{sub}[m]$$$), and each child subtree (size $$$\text{sub}[c]$$$ per child $$$c$$$).

Count $$$= \displaystyle\sum_{a \lt b \lt c} S_a \cdot S_b \cdot S_c$$$
Computed efficiently: for each branch $$$b$$$, add $$$S_b \cdot \bigl(\sum_{i \lt b} S_i\bigr) \cdot \bigl(\sum_{i \gt b} S_i\bigr)$$$ using prefix sums.
Total: $$$O(n)$$$ in a single DFS.

Count $$$T$$$ = total inversions in the string — the number of pairs $$$(i, j)$$$ with $$$i \lt j$$$, $$$s_i = $$$ '1', $$$s_j = $$$ '0'.

If $$$T$$$ is odd, Alice wins immediately.

If $$$T$$$ is even and there exists an index $$$i$$$ that is part of an odd number of inversion pairs, Alice can delete all characters except $$$i$$$.

The deleted subsequence has $$$T - (\text{inversions involving } i)$$$ inversions. Since $$$T$$$ is even and inversions involving $$$i$$$ is odd, the deleted part has odd inversions — a valid move. The remaining single character has $$$0$$$ inversions, so Bob cannot move. Alice wins.

When every index has an even number of inversion pairs: start with chosen $$$= \emptyset$$$ (0 inversions) and remaining $$$=$$$ full string ($$$T$$$ inversions) — both even.

Each time you move one character into the chosen set, it has $$$k_C$$$ inversion pairs with other chosen characters and $$$k_R$$$ pairs with remaining characters, with $$$k_C + k_R$$$ even. So $$$k_C \equiv k_R$$$: both sides flip parity together or neither does.

So chosen and remaining always have the same parity of inversions. If Alice picks a valid subsequence (odd inversions), the remaining string also has odd inversions.

If neither Hint 2 nor Hint 3 applies, then whatever Alice picks with odd inversions, Bob sees a remainder with odd inversions and can take everything — Bob wins.

$$$a_0$$$ cannot be changed — it has no left neighbor. So $$$a_0$$$ is always part of the answer range. Goal: bring all other elements as close to $$$a_0$$$ as possible.

Repeatedly subtract $$$a_0$$$ from $$$a_1$$$ until $$$a_1 \in [0, a_0)$$$, i.e. set $$$a_1 = a_1 \bmod a_0$$$. Then repeatedly subtract $$$a_1$$$ from $$$a_2$$$ until $$$a_2 \in [0, a_1)$$$, and so on — making the array non-increasing: $$$a_0 \geq a_1 \geq a_2 \geq \cdots$$$

Now add $$$a_0$$$ to all elements. Intermediate negative values are allowed. Subtract consecutive pairs right to left:
$$$[a_0, a_1, a_2, \ldots, a_{n-1}]$$$
$$$\to [a_0, a_1, a_2, \ldots, a_{n-2},\ a_{n-1} - a_{n-2}]$$$
$$$\to [a_0, a_1, a_2, \ldots, a_{n-3},\ a_{n-2} - a_{n-3},\ a_{n-1} - a_{n-2}]$$$
$$$\to \cdots$$$
$$$\to [a_0, a_1,\ a_2 - a_1,\ a_3 - a_2,\ \ldots,\ a_{n-1} - a_{n-2}]$$$

Now add left to right starting from $$$[a_0,\ a_1,\ a_2-a_1,\ a_3-a_2,\ \ldots,\ a_{n-1}-a_{n-2}]$$$:
$$$\to [a_0,\ a_1+a_0,\ a_2-a_1,\ a_3-a_2,\ \ldots]$$$
$$$\to [a_0,\ a_1+a_0,\ a_2+a_0,\ a_3-a_2,\ \ldots]$$$
$$$\to \cdots$$$
$$$\to [a_0,\ a_1+a_0,\ a_2+a_0,\ \ldots,\ a_{n-1}+a_0]$$$

Similarly, starting from $$$[a_0,\ a_1,\ a_2-a_1,\ a_3-a_2,\ \ldots,\ a_{n-1}-a_{n-2}]$$$, subtract $$$a_0$$$ from $$$a_1$$$ instead:
$$$\to [a_0,\ a_1-a_0,\ a_2-a_1,\ a_3-a_2,\ \ldots,\ a_{n-1}-a_{n-2}]$$$
Then add left to right:
$$$\to [a_0,\ a_1-a_0,\ a_2-a_0,\ \ldots,\ a_{n-1}-a_0]$$$

Since the array is non-increasing after Hint 2, all $$$a_i \in [0, a_1]$$$ for $$$i \geq 2$$$.
So in $$$[a_0,\ a_1+a_0,\ a_2+a_0,\ \ldots]$$$, every element satisfies $$$a_i+a_0 \in [a_0,\ a_1+a_0]$$$. Range $$$= a_1$$$.

Starting from $$$[a_0,\ a_1,\ a_2,\ \ldots,\ a_{n-1}]$$$, make $$$a_1 \to a_1 - a_0$$$ (a negative value). The new step size available to $$$a_2, \ldots, a_{n-1}$$$ is $$$a_0 - a_1$$$.

Since the array is non-increasing, all $$$a_i \in [0,\ a_1]$$$ for $$$i \geq 2$$$. By repeatedly taking $$$\bmod\ (a_0 - a_1)$$$, all $$$a_2, \ldots, a_{n-1}$$$ can be reduced to lie in $$$[0,\ a_0 - a_1]$$$.
Now add $$$a_1$$$ to each of $$$a_2, \ldots, a_{n-1}$$$: they move from $$$[0,\ a_0-a_1]$$$ to $$$[a_1,\ a_0]$$$. So $$$\min = a_1$$$, $$$\max = a_0$$$, range $$$= a_0 - a_1$$$.

The minimum achievable range is $$$\min(a_1 \bmod a_0,\ a_0 - a_1 \bmod a_0)$$$.

If $$$a_0$$$ divides $$$a_1$$$, the above arguments fail — the best we can do is make $$$a_1 = a_0$$$, contributing $$$0$$$ to the range. We then repeat the same argument for $$$(a_0, a_2)$$$, then $$$(a_0, a_3)$$$, and so on, skipping all multiples of $$$a_0$$$. The answer is determined by the first $$$a_r$$$ that is not a multiple of $$$a_0$$$. If no such $$$a_r$$$ exists, the answer is $$$0$$$.

For all subarrays: fix left endpoint $$$l$$$. Let $$$r$$$ be the first index $$$ \gt l$$$ where $$$a_r$$$ is not a multiple of $$$a_l$$$.

All subarrays $$$[l, l], [l, l{+}1], \ldots, [l, r{-}1]$$$ have answer $$$0$$$.
All subarrays $$$[l, r], [l, r{+}1], \ldots, [l, n{-}1]$$$ share the same first non-multiple $$$a_r$$$, so each contributes $$$\text{cost}(a_l, a_r)$$$.

Total contribution of $$$l$$$: $$$\text{cost}(a_l, a_r) \times (n - r)$$$.

To find $$$r$$$ for each $$$l$$$ efficiently: build a segment tree on $$$a$$$ supporting range GCD queries.
Binary search on the segment tree: find the first $$$r$$$ where $$$\gcd(a_l, \ldots, a_r)$$$ is no longer divisible by $$$a_l$$$. Use max_right from the AtCoder library for $$$O(\log n)$$$ per query.
Total: $$$O(n \log n)$$$.

Starting in August 2026, AtCoder will begin licensing user-submitted source code to AI companies for use as AI training data.

The licensed data will include not only submissions made after the start of the program, but also source code that has already been submitted in the past. However, any submission for which AI training has been explicitly opted out will not be included.

In connection with this change, we have updated our Terms of Service and Privacy Policy. We believe this data licensing program is necessary to ensure that AtCoder can continue providing programming contests free of charge in the future. At the same time, we do not believe that users should be required to allow their submissions to be used for AI training simply in order to participate in contests.

For this reason, we have introduced an opt-out setting for AI training use that applies to all submissions, as well as a separate opt-out setting that can be configured on a per-submission basis.

We have also provided a one-month grace period during which users can review and update their preferences.

If you do not want your submitted source code to be used for AI training or included in the licensing program, please make sure to update your settings before the grace period ends. For instructions on how to change your settings, please see the following page:

How to Opt Out of AI Training (Japanese) - AtCoderInfo (https://info.atcoder.jp/overview/about/ai-training-opt-out)

AtCoder will continue pursuing new initiatives to ensure that our programming contests remain free for everyone.

Thank you, as always, for your continued support of AtCoder.

https://atcoder.jp/settings/deny_learning

Do we really need to reorder more than once?

Any subtraction done after a reorder could have been done before it instead.
So optimal strategy is: subtract some elements, then reorder at most once.

Compute cost without reordering — check if $$$a_i \geq b_i$$$ for all $$$i$$$. Cost = $$$\sum (a_i - b_i)$$$.

Compute cost with reordering — sort both arrays. Pair largest $$$a_i$$$ with largest $$$b_i$$$, and so on.
Check feasibility. Cost = $$$c + \sum (a_i - b_i)$$$.

Why this pairing? If the largest $$$b_i$$$ is 20, at least one $$$a_i$$$ must be $$$\geq 20$$$. If the second largest is 10, at least two $$$a_i$$$ must be $$$\geq 10$$$, etc.

Answer is $$$\min$$$ of both costs. If both are impossible, output $$$-1$$$.

Try to simplify the identity $$$\gcd(\text{lcm}(a,b),\, \text{lcm}(b,c)) = \gcd(a,c)$$$.

Look at a single prime $$$p$$$. Let its powers in $$$a, b, c$$$ be $$$i, j, k$$$ respectively.
LCM takes max power, GCD takes min power. The identity becomes:

Left side simplifies to $$$\max(j,\, \min(i,k))$$$.
So the equation holds iff $$$j \leq \min(i, k)$$$.

$$$j \leq \min(i,k)$$$ for every prime $$$p$$$ means $$$b \mid a$$$ and $$$b \mid c$$$.

Triple $$$(a, b, c)$$$ is crimson iff $$$b \mid a$$$ and $$$b \mid c$$$.
For a fixed $$$b$$$, both $$$a$$$ and $$$c$$$ can be any of the $$$\lfloor n/b \rfloor$$$ multiples of $$$b$$$ up to $$$n$$$.

A guild $$$(v, h)$$$ is the set of nodes in the subtree of $$$v$$$ at distance exactly $$$h$$$ from $$$v$$$.
When is guild $$$(u, d)$$$ the same set as guild $$$(\text{child}, d-1)$$$?

If only one child's subtree has nodes at distance $$$d$$$ from $$$u$$$, then $$$(u, d)$$$ gives the same set as (that child, $$$d-1$$$). No new guild!

If at least two children have nodes at distance $$$d$$$ from $$$u$$$, no single descendant can reproduce the combined set. This is a new guild unique to $$$u$$$.

For each node $$$u$$$, let child subtree depths (max distance reachable from $$$u$$$ through each child) be $$$d_1 \geq d_2 \geq \ldots$$$

Guild $$$(u, d)$$$ is unique to $$$u$$$ for $$$d = 0, 1, \ldots, d_2$$$ — contributing $$$d_2 + 1$$$ guilds.
If fewer than 2 children, only $$$d = 0$$$ is unique — contributes 1.

Run a single DFS. For each node, sort child depths descending.
- If $$$\geq 2$$$ children: add $$$d_2 + 1$$$ to answer.
- Else: add 1.

Return $$$d_1 + 1$$$ to the parent. $$$O(n)$$$ per test case.

How many layers does $$$n = p^k$$$ require?
Divisors are $$$p, p^2, \ldots, p^k$$$. Each divides the next, so they must go in strictly increasing layers — exactly $$$k$$$ layers.

For $$$n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_r^{e_r}$$$, we need at least $$$e_1 + e_2 + \cdots + e_r$$$ layers (= powerSum).
Each step up in exponent sum forces a new layer.

The $$$r$$$ primes $$$p_1, \ldots, p_r$$$ are pairwise coprime, so no two can share a layer. They each need a dedicated layer.
For divisors with exponent sum $$$ \gt 1$$$, all of them can share one layer — arrange in a chain where adjacent numbers share a prime factor.

Total layers = $$$r$$$ layers for primes + one layer per remaining exponent sum level.

Use a linear sieve for $$$O(\log n)$$$ factorization per query.

Assume the final string is fixed (all N already replaced). How do we count mistakes?

Chell picks a segment $$$[l, r]$$$ and declares everything inside fake, everything outside real.
Mistakes = missed fakes + wrong reals
= F's outside $$$[l,r]$$$ + T's inside $$$[l,r]$$$

Now decompose missed fakes:
F's outside $$$[l,r]$$$ = total F's $$$-$$$ F's inside $$$[l,r]$$$

So: Mistakes = total F's $$$-$$$ F's inside $$$[l,r]$$$ + T's inside $$$[l,r]$$$

Now change F $$$\to +1$$$, T $$$\to -1$$$. Then:
- F's inside $$$[l,r]$$$ contribute $$$+1$$$ each to $$$\text{sum}(s[l..r])$$$
- T's inside $$$[l,r]$$$ contribute $$$-1$$$ each to $$$\text{sum}(s[l..r])$$$

So $$$\text{F's inside} - \text{T's inside} = \text{sum}(s[l..r])$$$, which gives:

Since $$$F_{cnt}$$$ is fixed for a given string, Chell minimizes mistakes by choosing $$$[l,r]$$$ to maximize $$$\text{sum}(s[l..r])$$$.

This is exactly the maximum subarray sum, solvable in $$$O(n)$$$ with Kadane's algorithm.

GLaDOS controls the N replacements and wants to maximize $$$F_{cnt} - \text{maxSubarraySum}$$$.
Kadane's algorithm tracks two values as it scans left to right:
$$$c$$$ — max subarray sum ending at current position (reset to 0 if negative).
$$$m$$$ — max subarray sum seen so far.
So we enumerate N-replacements while tracking $$$(f,\ m,\ c)$$$ where $$$f$$$ = no of F's placed so far.

$$$O(n^4)$$$ DP — 3D boolean state:
$$$dp[f][m][c]$$$ = True if tuple $$$(f, m, c)$$$ is reachable, False otherwise.
Initial state: $$$dp[0][0][0] = \text{True}$$$, all others False.

Transitions for each character (explore both branches when N):
Place T: $$$f' = f,\quad c' = \max(0,\ c-1),\quad m' = \max(m,\ c')$$$
Place F: $$$f' = f+1,\quad c' = c+1,\quad m' = \max(m,\ c')$$$

Answer $$$= \max$$$ over all reachable $$$(f, m, c)$$$ of $$$(f - m)$$$.
$$$O(n^3)$$$ states $$$\times$$$ $$$O(n)$$$ characters $$$= O(n^4)$$$ total.

$$$O(n^3)$$$ optimisation — remove $$$m$$$ from the state dimension:
For fixed $$$(f, c)$$$, the answer contribution is $$$f - m$$$. Since $$$f$$$ is fixed, we want to minimise $$$m$$$.
So instead of a 3D bool, store the minimum achievable $$$m$$$:
$$$dp[f][c]$$$ = min $$$m$$$ over all reachable N-replacements so far.
Initial state: $$$dp[0][0] = 0$$$, all others $$$= \infty$$$.

Transitions (both branches when N):
Place T: $$$f' = f,\quad c' = \max(0,\ c-1),\quad m' = \max(dp[f][c],\ c')$$$
$$$\quad\quad dp[f'][c'] = \min(dp[f'][c'],\ m')$$$
Place F: $$$f' = f+1,\quad c' = c+1,\quad m' = \max(dp[f][c],\ c')$$$
$$$\quad\quad dp[f'][c'] = \min(dp[f'][c'],\ m')$$$

After processing all characters:

$$$O(n^2)$$$ states $$$\times$$$ $$$O(n)$$$ characters $$$= O(n^3)$$$ total.

What is the smallest possible final height that all towers can reach?

Remember that every tower must receive a strictly positive increment.

If the tallest tower has height mx, can the final height be mx?

Try making every tower equal to mx+1.

For a tower of height h[i], how much do we need to add?

The answer is determined by the tower requiring the largest increment.

Look at the leftmost character that is still equal to '1'.

How many operations can affect position i?

When processing position i, there is only one remaining operation that can flip it.

If s[i]='1', you are forced to use the operation starting at i.

Process positions from left to right greedily.

After fixing the first n-k positions, what must be true about the remaining k positions?

Would you ever want to perform +1 before a division?

Compare: ($$$\frac{a+1}{x}$$$) vs ($$$\frac{a}{x} + 1$$$)

Any addition done before division becomes less valuable afterwards.

Assume all division operations happen first.

How many times can a number be divided by x before reaching 0?

Try recursively considering: - stop dividing and use additions - divide the larger number once more

The recursion depth is only O(log(max(a,b))).

Think in terms of winning and losing game states.

Suppose the current chosen value is x. What future values can be picked?

A state is winning if it can move to a losing state.

Sort the values first.

Process values from largest to smallest.

For value x, you need information about states in [x,x+k].

Can you maintain winning/losing information using a range-query data structure?

When is a segment a permutation of consecutive integers?

All elements must be distinct.

If mn and mx are minimum and maximum values, what relationship must hold with the segment length?

A good segment satisfies: mx — mn + 1 = length.

Imagine splitting the array into a left part and a right part.

Store all good segments completely inside the left part.

While extending a segment on the right, check whether the complementary value range already appeared on the left.

Enumerating split positions leads to an O(n²) solution.

Let's first ignore the divisibility condition.

Suppose we have already chosen p₁, p₂, ..., pₙ.

What does

LCM(p₁,p₂,...,pₙ) = p₁ × p₂ × ... × pₙ

actually mean?

Whenever you see LCM and Product together, try looking at one prime factor at a time.

Fix a prime p.

Let vᵢ be the exponent of p inside pᵢ.

For this prime:

Exponent in LCM = max(v₁,v₂,...,vₙ)

Exponent in Product = v₁ + v₂ + ... + vₙ

Since K = 1 in F1, the condition becomes:

max(v₁,v₂,...,vₙ) = v₁ + v₂ + ... + vₙ

Try a few examples.

✓ [3,0,0]

✓ [0,0,0]

✗ [2,1,0]

✗ [1,1,0]

When can maximum of several non-negative numbers be equal to their sum?

This happens iff at most one exponent is positive.

For every prime p, all copies of p must belong to at most one chosen number.

Now use the condition: pᵢ divides aᵢ

Suppose exponent of prime p inside aᵢ is cᵢ.

For this prime, we have two types of choices:

• Do not use p anywhere.
• Choose exactly one index i and place a positive exponent there.

If index i is chosen, how many possible exponents can be assigned?

Remember that exponent inside pᵢ can be anything from 1 to cᵢ.

Contribution of index i is therefore cᵢ.

Adding the option of not using the prime at all gives:

1 + c₁ + c₂ + ... + cₙ

Different primes are completely independent.

Solve the counting problem separately for every prime factor.

Factorize all aᵢ.

For every prime p, compute:

1 + (total exponent of p across all aᵢ)

What is the exponent of p in: LCM(p₁,p₂,...,pₙ)?

What is the exponent of p in: p₁×p₂×...×pₙ?

You should obtain: max(vᵢ)+vₖ = Σvᵢ

Each aᵢ only gives an upper bound on vᵢ.

DP over: (current maximum exponent, current sum of exponents).

Let's first forget about the tree.

Suppose the array is just a normal sequence.

When does

XOR(segment) = SUM(segment)

hold?

Think about how binary addition works.

SUM differs from XOR exactly because of carries.

Try a few examples:

1 + 2 = 3 and 1 XOR 2 = 3 ✓

3 + 1 = 4 but 3 XOR 1 = 2 ✗

What changed?

A carry appears whenever two numbers contain a common set bit.

Therefore:

XOR(segment) = SUM(segment)

iff no bit position appears in more than one element of the segment.

Equivalently, if we maintain bitwise OR of the segment, then every bit can appear at most once.

Think of every bit as a resource that can only be used by one element.

Now ask yourself:

How long can a valid segment actually become?

There are only about 20 bits available.

Whenever a bit repeats, the segment immediately becomes invalid.

This means the number of distinct valid prefixes/suffixes starting from a node is actually very small.

This bounded number of states is the key observation that makes the problem solvable.

A naive path can be very long, but the number of distinct valid XOR/SUM configurations remains small.

Now bring the tree back.

Each query asks for the number of valid subsegments on the path between two vertices.

Many path-query problems on trees can be solved by processing queries around a centroid.

Can we count all valid segments whose path passes through a particular centroid?

Suppose a path passes through centroid c.

Such a path can be decomposed into:

(node in subtree A) → c → (node in subtree B)

For every node, store all valid prefixes ending at the centroid.

Because valid prefixes are short (Hint 6), the amount of information per node remains small.

While processing one subtree, keep information from previously processed subtrees.

Then count how many pairs of prefixes can be merged through the centroid while still having no overlapping bits.

The merge condition is exactly the same as before:

No bit may appear twice.

So while combining two sides of the path, check whether their bitmasks are disjoint and also compatible with the centroid value.

Using centroid decomposition:

• Every query is assigned to O(log n) centroids.
• Every stored prefix/suffix state is small because the number of usable bits is small.

This gives an overall complexity roughly

O((n + q) log n · maxBits).

When do we really need +1 step?

To reach 8, we can do 2+2+2+2
But to reach an odd number, we must need +1. Ex 9 = 2+2+2+2+1

Now, if both x and y are odd, we will need two +1 step

Chosing substring is red herring, we can chose the complete string.

What is the most simple regular bracket string?
(((((((( ))))))

Check if this string is regular bracket sequence or not.

When is a number divisible by 6?
If a number is divisible by both 2 and 3, then only its divisible by 6.

Each number in array belongs to one of following category -
- Not divisible by 2 and not divisible by 3
- Divisible by 2 but not divisible by 3
- Not divisible by 2 but divisible by 3
- Divisible by both 2 and 3

For a subarray product to be divisble by 6, atleast one number must be divisible by 2 and atleast one number must be divisble by 6.
These two numbers can be same as well.

First try to place numbers divisible by 6.
Subarray they are part of will always be divisible by 6.
So we should try to place it at a position that touches minimum no of subarrays.

Count the no of subarrays 6 is part of -
* * * * * 6 * * * * * *
* * * * * * * * 6 * * *
* * * * * * * * * * * 6

We should place 6 at last position, and then try to solve for remaining array.

After placing all multiples of 6.
Remaining nos are either divisible by 2 or 3 or none.
Subarray will be divisible by 6 if it contains multiples of both 2 and 3.
Similar to 6, we should try to place them as far as possible.

* * 2 * * * 3 * * * * * *
* * 2 * * * * * * * 3 * *
2 * * * * * 3 * * * * * *
2 * * * * * * * * * * * 3

Optimal way is to put 2 in front and 3 at last.

Overrall we should put nos in following order -
- Not divisible by 2 and not divisible by 3
- Not divisible by 2 but divisible by 3
- Divisible by 2 but not divisible by 3
- Divisible by both 2 and 3

Look at the definition of MEX ==> Smallest non negative no not present in array.

If our array does not contains 0, then MEX will be 0

So, to make MEX > 0, then we must chose 0

We can have following palindromes for 0.
- Only one zero is used -
* * * * * 0 * * * * *
Then it should have odd length and 0 is in the middle.
- Both zero match with each other.

• Only one zero is used -
  * * * * * 0 * * * * *
  Start with one 0, and try to extend it on both sides

• Both zero match with each other.
  First check if the string starting and ending with 0 is a palindrome.
  Then try to extend it on both ends.

Lets first try to find answer without doing any operation.

5th cube in 6th column will change its location if there exists a colmn after 6 with less than 5 cubes.
Alternatively, 5th cube in 6th column will not change its location if every colmn after 6 has >= 5 cubes.

No of cubes in 6th column that change location = Total cubes in 6th column — cubes that do not change location

Cubes that do not change location in 6th column is `$$$\min(a_6,a_7,....,a_{n-1})$$$

For finding no of increased location, we can look at each element and how many column this will impact aka for how many column this acts as minimum.

Similar to E, lets first try to find sum of distances without doing any operation

Lets try to find final configuration, and lets call it b.

Final configration b is simply sorted array a.

Instead of finding sum of distances, lets look at this in a different way.
For each row i, lets count how many cubes will cross the junction between ith column and i+1th column.

We can find this sum for all i, and this will give us required distance.

How many cubes cross junction between ith column and i+1th column?
This is no of cubes initially present in 1....ith column — no of cubes that still remain in 1...ith column
Essentially, $sum(a[0...i]) — sum(b[0....i])

Now, for counting result after 1 operation, for each element you can take difference between its current location, and its location in b

Lets try to find bare minimum must have conditions, to reduce to one element.

Notice following thing -
- If array length is even, then it cannot be made of size 1. Why??
- Due to $$$x = c_{i-1} - c_i + c_{i+1}$$$ condition all numbers are always +ve.

Try to play around odd length array, and try to reduce it to length 1 ignoring $$$c_{i-1} + c_{i+1} \gt c_i$$$ condition.

Another critical observation -
You will realise that last single element is always same. It doesnt really matter what is the sequence of operations

The value of this last element is equal to sum of elements at odd index — sum of elements at even index

If all the elements are always +ve then element remaining at last should also be +ve.

Now, try to prove this is sufficient condition too.
If sum of elements at odd index > sum of elements at even index, then we will be able to always find operations, until sequence length becomes 1.

Lets first solve for case when we have even no of leaf.

For each edge, lets try to find the minimum no of pairs that cross it.

Each edge will split tree into 2 disjoint tree.
If both of these components contain even no of leaf, then we can match pairs within them.
So, we can ensure this edge is not used.

If both of these components contain odd no of leaf, then we can match almost all of pairs within them, but we will still be left with one node on each side.

To path connecting these remaining node will contain current edge. So, we must chose this node.

For odd no of leaf, follow up on previous idea — use DP on Trees

Find the length n of the string, and then print first n-2 chars and then i.

Let n be the length of the string.
Answer is either 1 or n

If there exists adjacent 2 equal chars, we can reduce the string to length 1.
The idea is we remove these 2 equal chars, and then replace them with one nearby char, thereby ensuring that we still have 2 adjacent equal chars.

Greedy.
For each i, try to find a minimum value of ai which we can get and it is still sorted.

If K is the minimum possible value of a_{i-1} we can get such that the array is still sorted.

If we do not do any operation the value remains ai. This is possible only if K <= ai

If we do an operation then bj — ai >= K, this imples aj+K <= bj.
So chose the minimum bj >= aj+K, and do an operation using it.

Score of an array is sum of prefix sum of the array.
For an index idx = i*m+j, S_{idx} = sum of first i-1 arrays + sum of first j elements of ith array.

Try to find both of these values separately.

Contribution due to part 2 is sum of score of all arrays.

Let C = [sum(a1),sum(a2),sum(a3),...,sum(an)]
Let S = maximum score we can get after rearranging C.
Then contribution due to part 1 is m*S

max(x-y,y-x) is equal to abs(x-y)
First try to find trivial -1 cases.

Look at the complete string first. The score is abs(n-m).
If this is more than K, then maximum balance among all substring is more than K.

If n<k and m<k, then balance can never be equal K.

Otherwise the following string works for N=10, M = 11, and K = 3
111 000 111 000 111 000 11 0

If an array has a majority element, then there must exist a subarray with length 2 or 3 with that element being majority.

The problem reduces to checking length 2 and 3 paths.

Length 2 paths are just edges.

For length 3, you can fix a middle element and check if 2 adjacent elements contain same value.

There arent many cases when lcm is semi prime.

If p and q are different prime nos, then their lcm p*q is semi prime.

Otherwise, one of the element must be semi prime, and other one must be its factor.

f(t) can also be written as 1 + no of adjacent different chars.

Lets look contribution due to si and sj being adjacent.
If si==sj, they add 0 to score.
If si!=sj, then they add 1 to score.
No of subsequences that contain si and sj adjacent are pow(2,i-1)*pow(2,n-j), basically,
- For char before i, we have 2 choices we can take them or ignore them.
- For char after j, we have 2 choices we can take them or ignore them.
- We must take i and j
- We must not take chars between i and j

Now, the hard part, how to do it with changing chars?
Use Segment tree.

For each node representing s[i...j], we can maintain -
- Sum of pow(2,i-1) when si = 0
- Sum of pow(2,i-1) when si = 1
- Sum of pow(2,n-j) when sj = 0
- Sum of pow(2,n-j) when sj = 1
- Contribution due to pairs inside this segment

Change percent cutoff to -1 for every color, and 100 for cyan.

Set permutateUsernames variable to true

Assume $$$b_{n+1}=0$$$.
Monocarp should solve problems on day i only if $$$a_i \gt b_{i+1}$$$.
For all such days, find sum of difference.

Let $$$d=a+b+c$$$.
Monocarp will travel d km every 3 days.

So you will need a minimum of $$$3*n/d$$$ days.

The required no of days is between $$$3*n/d$$$ and $$$3*n/d+3$$$; check all 4 possibilities.

Result is one of 3 possibilities
1. All are 1
2. All are 0
3. Only one 1 and the rest all are 0

Try to figure out conditions for all these cases.

Based on the sum of all array and x,y, first, find the minimum and the maximum possible sum of $$$a_i+a_j$$$.

Count Pairs Whose Sum is Less than Target

There are many ways to solve this problem.
The optimal price will always be some ai,bi.

First, use Coordinate Compression to reduce the range of ai and bi.

Now, for each point, using your favourite range sum data structure, you can find how many people will buy at that price and how many of them will leave a -ve review.

Explicitly maintain range of intervals where joker can exist, based on these ranges find new ranges.

The crux of the problem is at any point, there will be atmax 3 different such intervals.

Introduce a new n+1th snake.
For each pair of snakes, L and R, find the minimum distance between them.

Now this is a Travelling salesman problem

We can do one of the following 2 things -
- Either write both strings without using 2nd action
- Or we first write longest common prefix string, then use 2nd action and then write the remaining strings.

Use pen and paper and write down table C.

Table C looks like this -

1             
1 1              
1 2 1              
1 2 4 1            
1 2 4 8 1             
1 2 4 8 16 1             

If $$$k=n$$$, $$$C[n][k] = 1$$$, else $$$C[n][k]=2^k$$$

Sort the array and then use two pointers

Alternatively,
Sort the array and then for each fixed L, binary search largest R such that you can take all elements in subarray [L...R]

dp[i][x][y] denotes maximum checks among first i queries that we can pass if our current intelligence level is x and current strength level is y.

Its never optimal to leave any acquiring point. So x+y will always be no of rj=0 for j<=i.

This allows us to remove one dp dimension.

dp[i][y] denotes maximum checks among first i queries that we can pass if we have used y attribute points for strength, and all remaining points for intelligence.

Whenever we have ri < 0, we essentially do +1 to a suffix in above dp array.
Whenever we have ri > 0, we essentially do +1 to a prefix in above dp array.

For ri=0,
If we increase strength, we can do dp[i][y]=max(dp[i][y],dp[i-1][y-1])
If we increase intelligence, we can do dp[i][y]=max(dp[i][y],dp[i-1][y])

If we use lazy segment tree for range addition.
We can solve this problem in $$$O(m^2*logm + n*logm)$$$.
$$$O(m*logm)$$$ per attribute point query, and $$$O(logm)$$$ per check query.

We can even do better, without using any segment tree.
Lets maintain difference array for dp[i][*] table.
So range additions are just +1 and -1 at 2 places.

Allowing us to do this O(m^2+n).

Refer implementation for more details.

Lets pick a suite and distribute m cards in descending order.

Lets say we have distributed all cards between [i...m], we have given p1 cards to first player and p2 cards to second player.
Let Y denotes minimum no of suite 1 cards we need for this assignment.
Let dP = p1-p2

Now, we can use dp here,
dp[i][dP][Y] denotes above state.

Y is essentially minimum possible value of dP when we are assigning all the cards.

The transitions are as follows -
If we assign i-1 card to first player dp[i-1][dP+1][Y]+=dp[i][dP][Y]
If we assign i-1 card to second player dp[i-1][dP-1][min(Y,dp-1)]+=dp[i][dP][Y]

Another important observation is we can only give away equal no of cards to both the player if dp=Y for every suites except 1, ie we only need dp[1][X][X]

Another important observation is -
No of suite 1 cards assigned to first player >= No of suite 1 cards assigned to second player.

For all other suites 2<=j<=n,
No of suite j cards assigned to first player <= No of suite j cards assigned to second player.

Now, we can first fix the no of extra suite 1 cards (say K) we want to give to first player.

Let the no of extra cards given to second play for other suites be x2,x3,...,xn.

Then we need x2+x3+...+xn = K.
This part can be done using knapsack.

Its possible to solve this problem for following constraints -
- N <= 10^18
- M <= 500

Let first decide if we want to do an operation on xi or yi.

We can ensure that each ai is either 0 or 1.
Do -1 if ai is 1, and +1 if ai is 0.

Now, lets create a graph with n nodes and q edges.
ith edge connects xi and yi.

Selecting xi or yi for each query is equivalent to giving a direction to each edge in this graph.

If edge is directed from xi -> yi, we select xi.
If edge is directed from yi -> xi, we select yi.

au will be equal to parity of no of incoming edges on u.

Formally, we have a graph with n nodes, and q edges.
We want to assign direction to each edge such that no of nodes with odd parity of incoming is minimum possible.

This is quite a well known problem (CodeChef EDGEDIR), and have appeared quite many times.

For each connected components, if no of edges is odd, then its possible to direct edges in such a way that only one node has odd parity of incoming edges.
For each connected components, if no of edges is even, then its possible to direct edges in such a way that all nodes have even parity of incoming edges.

In each second, we will blend $$$\min(x, c)$$$ fruits. So time taken is $$$\displaystyle \left \lceil \frac{n}{\min(x, c)} \right \rceil$$$

$$$n$$$ is the winner. $$$n-1$$$ will lose only against $$$n$$$.

For others, if we make them first against $$$n-1$$$ and atlast we have $$$n-1$$$ and $$$n$$$ fight, their score will be added.

So the final answer will be $$$A_1+A_2+....+A_{n-2}+A_{n}-A{n-2}$$$

Let's say we know some string $$$s$$$ is a substring of $$$t$$$.
How can we extend it to find char just after this?

The idea is to query for $$$s0$$$ and $$$s1$$$; if one of them returns true, add that char to s and continue again.

If both $$$s0$$$ and $$$s1$$$ return false, then we know that our current string is the suffix of $$$t$$$. Now query for $$$0s$$$ and $$$1s$$$. and keep adding it in front.

In the worst case, this make take $$$2n+2$$$ queries. To avoid this, if $$$0s$$$ returns true, add $$$0$$$ in front. Otherwise, we know $$$1s$$$ will return true, so directly add it without asking.

What is the minimum possible value of the whole array?

One of the value must be less than or equal to the average of the array.

Now, notice that we only do -ve operations on the first element.
What is the minimum possible value of a2....,an?
(Again, think an average of a2....,an)

Similarly for every i, we will reduce (a1,a2,....ai-1) can only increase values in (ai,ai+1,.....,an).
So, what is the minimum value in this part?
(Again think average of ai,....,an)

Now, if we take the minimum of all of the above values, we know for sure that the final minimum is less than or equal to the above value.
As it turns out always possible to create an array such that above value will be the minimum possible.

Do similar stuff for maximum value and print their difference.

What is the minimum value we can have first value? Take minimum.

Now, for the second element, find the element such that gcd(p1,ai) is the minimum possible.

In general, it greedily finds the next value such that gcd reduces as much as it can.

Well. Why does this greedy works?

Proof by AC

Smash me

Let's pick this graph, and say we want to find the answer when Bob starts at node 8.

The game will proceed as follows: both Alice and Bob will move towards each other on the path between 1 and 8.
At some point, one of them will leave this path, allowing another person to take all remaining nodes if they want.

We don't really need a complete tree, just the distances of how long someone can go if they leave this path. The depth array ($$$d_1,d_2,...,d_k$$$) becomes $$$[0,2,1,4,1,2,1,4]$$$

Now, if Alice leaves at node 2, then they will travel a total of 4 nodes. We can

Now, if Alice leaves at node 2, then they will travel a total of 4 nodes.

Formally, if Alice leaves at ith node on this path, the distance she will travel is $$$i+d_i$$$ These will be distances for the example above. $$$[1,4,4,8,6,8,8,12]$$$

If Bob leaves at ith node on this path, the distance he will travel is $$$k-i+1+d_i$$$ These will be distances for the example above. $$$[8,9,7,9,5,5,3,5]$$$

Now, we can brute force game theory problem. FindWinner(aliceIdx,bobIdx,Turn) denotes who will be the winner if Alice is at aliceIdx on path, Bob is at bobIdx on path, and turn is (Alice/Bob) based on who is going to play.

At each turn player can see who will be the winner if they leave the path, and if they do not, and make a rational decision based on it.

Roughly, the following is the pseudo code -

// returns true if Alice wins, and false if Bob wins.
bool FindWinner(const lli aidx,const lli bidx,const bool isAliceTurn){
    if(isAliceTurn){
        // if Alice continues on the path.
        if(aidx+1<bidx&&FindWinner(aidx+1,bidx,!isAliceTurn))
            return true;
        // if Alice leave at current node.
        // You can use segment tree for this range max query.
        if(aliceDist[aidx]>max(bobDist[aidx+1:bidx]))
            return true;
        return false;
    }

    // if Bob continues on the path
    if(aidx+1<bidx&&!FindWinner(aidx,bidx-1,!isAliceTurn))
        return false;
    // if Bob leave at current index.
    // You can use segment tree for this range max query.
    if(bobDist[aidx]>=max(aliceDist[aidx:bidx-1]))
        return false;
    return true;
});

My rating doesn’t allow me to understand it.

Maintain current amount of gold Robin has. Process all ai.

• If ai>=k, increase counter by ai
• If ai==0 and we have some gold, decrease current gold by 1 and increase answer.

On last day only leaf grown between n-k+1 and n day will remain.

pow(i,i) is odd if i is odd, even if i is even.

We need no of odd numbers between n-k+1 and n

Answer is impossible if n less than 3.

Lets first find minimum no of people that should be unhappy (say K).

Lets sort A, now average should be more than 2*Ak

Lets say pot has X gold.
Let S be the total gold.

$$$2*Ak \lt (S+X)/N$$$
$$$2*N*Ak \lt S+X$$$
$$$2*N*Ak-S \lt X$$$
$$$2*N*Ak-S+1 \le X$$$

So X should be max(0,2*N*ak-S+1)

For each starting day lets find how many jobs it overlaps with.

Two Pointers

In addition, h of the n vertices each has a single horse available.

Just forget this condition exists, and assume each place contains unlimited horses.

Now for each place try to find the minimum time, if we reach there using a horse, and without a horse.

Try to solve above problem using a modified version of Dijkstra's algorithm

At last fix a meeting point, and take maximum of minimum time each person takes to reach there with or without horse.

DP on trees

For each subtree dp1[u] denotes the best possible sum we can get if we consider only subtree of u and u is destroyed.
For each subtree dp2[u] denotes the best possible sum we can get if we consider only subtree of u and u is not destroyed.

Lets first process each day one by one.

We should maintain list of all drinkable milks in a map.
We should remove all non drinkable milk.
We should add all the new milk we have got today.

Now split into 2 cases —

• Latest milk quantity is less than m.
• Latest milk quantity is atleast m,

For case 1, when latest milk quantity is less than m,
We should bruteforce by taking latest milk and until we have total m, or no milk remains.

Then increase time by 1.

For case 2, when latest milk quantity is atleast m,

Here, lets try to find how long can we drink current milk.

We can drink it until —

• Some other milk comes
• If current quantity is C, then we can drink it for next C/m days
• If this milk came on dj day, we can drink it until dj+k-1 day

Take minimum of these 3, and assume we have gotten m milk each day.
Then remove this quantity from latest milk, and increase time.

Lets say we are playing game on targets B1,B2,B3,...,Bm
What is the optimal strategy for players?

Players should always chose the maximum target.

Lets sort B in descending order.
Then Robin takes B1,B3,B5... and Sheriff will take B2,B4,....

Because B1 \ge B2, B3 \ge B4, and so on...
At this point, Sheriff can never win.
When can we have a draw?

We will have a draw if and only if no of targets is even, and B1 = B2, B3 = B4, and so on...

In other words, frequency of every no in B should be even.

How to check if frequency of every no is even?
Zobrist Hashing

Lets fix the count of aeiou $$$C_a,C_e,C_i,C_o,C_u$$$
What is the minimum number of subsequence palindromes?

No of palindromes that consist of only a is $$$2^{C_a}-1$$$ and similarly for eiou.
So lowerbound on no of palindrome is $$$2^{C_a}+2^{C_e}+2^{C_i}+2^{C_o}+2^{C_u}-5$$$
Does there exists a permutation where this lowerbound is achievable?

This lowerbound is achieved on strings of form aaaaaaaaaeeeeeeeeeeiiiiiiiiiioooooooooouuuuuuuuu

How to find optimal values of $$$C_a,C_e,C_i,C_o,C_u$$$?

In optimal answer $$$|C_x-C_y| \le 1$$$.
You can try to prove it using exchange arguments technique.

Separately solve for cases when David is on left side of both the teachers, in between the teachers and right side of both the teachers.

We need the nearest teacher on the left side and right side, and then B1 solution works.

To find the nearest teachers, you can either use binary search or use lower_bound stl function.

Let's first simplify the scoring function.

Let's say we have fixed string $$$t$$$, you do we find the score?
Let the no of narek strings formed is $$$c$$$ and total no of chars narek is $$$t$$$.
No of chars found by chatgpt will be $$$t-5*c$$$.
The score is $$$5*c-(t-5*c) = 10*c-t$$$.

Another way to see this cost function is -
Chatgpt will reduce score by -1 whenever it finds any of the char narek.
We will increase by +10 whenever we complete the string narek.

Now, $$$dp[i][j]$$$ can be the maximum score so far such that we have processed the first $$$i$$$ string, and we have got the first $$$j$$$ chars of uncompleted narek string (which is required for +10).

Use Minimax Algorithm

Let's say we know what positions a player playing $$$i+1$$$ can select and still win the game.
Can we use this information to find all the positions that a player playing $$$i$$$ move can select?

A player selecting $$$r,c$$$ on the move $$$i$$$ wins the game if and only if there is no position in $$$[r+1...n][c+1...m]$$$ which player playing $$$i+1$$$ move can select and win.

With careful implementation, one can solve the above problem in $$$O(N*M*L)$$$ time complexity.

First solve E1.

Consider the following testcase -

1 2 2
2 2 1
2 3 3

If a player has to select $$$2$$$ from somewhere, they should only select $$$(1,3)$$$ or $$$(2,2)$$$ or $$$(3,1)$$$.
Selecting $$$(2,1)$$$ instead of $$$(2,2)$$$, will just increase no of possible moves for the opponent.

We should ignore the nos not present in A.
For each nos present X in A and each column C, we can precompute maximum R such that $$$B[R][C]=X$$$.

Now, we should play this game only on these indexes.
With careful implementation on can solve it in $$$O(N*M+N*L)$$$.

• No of ones must be even.
• If no of ones is zero, then no of twos must be even.

These are necessary and sufficient conditions.

If it is a square matrix, then N must be a perfect square.

If N is a perfect square, then R=C=Sqrt(N).

Now, we can create R*C beautiful matrix, and then create required string.
Then check if it is equal to given string.

Lets try to create array greedily.

$$$A_1=L$$$,
$$$A_i-A_{i-1}=i-1$$$ for all $$$2 \le i$$$,

In general, after simplification,
$$$A_i=L+(i-1)*i/2$$$ for all $$$2 \le i$$$.

Longest array length depends only on $$$R-L$$$.
We need the largest $$$N$$$ such that $$$N*(N-1)/2 \le R-L$$$.

Permutation cycle

Create a graph with edge $$$i - \gt p_i$$$, and notice that each connected component is a cycle.
For each connected components count the no of black nodes, and then update this count for all nodes.

Solve for N = even first.

We should look at chars at odd index and even index.
Greedily chose the one that appears maximum no of times, and replace all the other chars.

For N = odd, we can iterate on index i that needs to be deleted.
Chars at odd index before index i we will remain at odd index, and chars at even index after i will move to odd index.

One can either use sliding window or prefix sum to find new frequecies at odd and even index after deleting char at index i.

We should find sum of product of all pairs, then we can divide by $$$N*(N-1)/2$$$ for expected value.

$$$ \sum_{i=1}^{n} \sum_{j=1}^{i-1} a_i*a_j$$$
$$$ = \sum_{i=1}^{n} a_i *(\sum_{j=1}^{i-1} a_j)$$$

You can now iterate on index i, and maintain a running sum of all the index before it.
Use this sum and $$$a_i$$$ to find sum of product of all pairs.

Solve for $$$N=2$$$ first.

Forget about $$$K$$$, and try to find smallest two positive nos you can have in the array.

Use only $$$a_i = a_i - a_j$$$ operation.

Let $$$u \ge v$$$.
If we repeatedly doing $$$u = u - v$$$, as long as we can.
We will end up with $$$u = u \mod v$$$.

This algorithm now sounds familiar?

Euclidean algorithm

The two nos you will end up will be $$$\gcd(a_1,a_2)$$$ and $$$\gcd(a_1,a_2)$$$, then we can change them to $$$0$$$ and $$$\gcd(a_1,a_2)$$$

Now, we can generalise this, and say we will end up with $$$n$$$ times $$$\gcd(a_1,a_2,...,a_n)$$$

We can change one of these to $$$0$$$, and for remaining we can do, $$$a_i = a_i + a_j$$$ operation to obtain first $$$N-1$$$ multiples of gcd.
Then check which is the kth smallest missing no.

$$$a_i = a_i + a_j$$$, this operation only changes the value which is larger.
So if we change any no to $$$0$$$, we can never increase it.

This was the reason why constraints were change to $$$1 \le a_i$$$.

Thanks neal and Dominater069 for flagging earlier hints I had were wrong.

Because we want smallest median, we should do operation as long as we can.
We will end up with $$$a_i = a_i \mod x$$$

Binary search for the median, and try to find how many nos can be $$$\le \text{mid}$$$.

To get this count, we need count of nos in range $$$[j*x,j*x+\text{mid}]$$$.
We can find this sum in $$$O(N/X)$$$ using prefix sum
With overall time complexity $$$O(N/X)*\log X$$$.

Queries can contain repeated $$$X$$$, but memorise the result for so that you do not have to find it again.
This will lead to $$$N*\log^2N$$$ time complexity.

Solve with $$$K=2$$$ only.

Turtle wants to maximise the remaining value, so he should try to remove the smallest values.
Similarly Piggy wants to minimise the remaining value, so he should try to remove the largest values.

Try to find bad pairs.

Some of the bad substring are.
- aaaabbbbb
- aabb
- ab

Some of the good substring are.
- ababababb
- abab

Intuitively, we should try to create a string which does not contain equal chars together.

Lets pick an array $$$B_1,B_2,...,B_M$$$, and see what happens when we do operation of X, with this array.
Let $$$\text{sm1}$$$ be the smallest missing value in B, and $$$\text{sm2}$$$ be the second smallest missing value in B.

Now, if $$$X=sm1$$$,
$$$\text{mex}(\text{X}, B_1, B_2, \ldots, B_M) = $$$
$$$\text{mex}(\text{sm1}, B_1, B_2, \ldots, B_M) = sm2$$$

otherwise,
$$$\text{mex}(\text{X}, B_1, B_2, \ldots, B_M) = sm1$$$

Now, we can model it as a graph problem,
Graph consists of $$$m+1$$$ nodes labelled with $$$0,1,...,m$$$
From any node we can reach $$$\text{sm1}$$$, and from $$$\text{sm1}$$$ we can reach $$$\text{sm2}$$$.

Our goal is to find for each node, maximum labelled we can reach starting from it.

We cannot create a graph of size $$$m+1 = 10^9 + 1$$$.
Let $$$K=\max(sm2)$$$ ie $$$K$$$ is maximum value of second maximum among all arrays given in input.

Notice that maximum X, we can reach after doing any operations is $$$K$$$.
So for all $$$i \gt K$$$, we should not do any operations, and $$$F(i)=i$$$.

Now, we can directly, calculate sum of i more than $$$K$$$ and create a graph with $$$K+1$$$ nodes.

Next observation was, from $$$X$$$, we will go to smaller value only once.

Refer hints of D1.

Because we cannot use same array twice, the only difference it makes it,
If from $$$X$$$ we go to $$$\text{sm1}$$$ of an array, we will not be able to go to $$$\text{sm2}$$$ with the same operation.
So we should reach $$$\text{sm1}$$$ using some other array, if it exists.
If such an array does not exists, we will not be able to reach $$$\text{sm2}$$$ using this operation.

First solve for case $$$L_1=1, R_M=N$$$ and $$$R_i + 1 = L_{i+1}$$$, ie every element is part of some range.

For each range lets fix $$$K_1,K_2,K_3,...,K_M$$$, and see how does an interesting permutation looks like.

Let $$$P_1=K_1-L_1+1$$$, $$$P_2=K_2-L_2+1$$$, and so on...
Similary let $$$S_1=R_1-K_1$$$, $$$S_2=R_2-K_2$$$, and so on...

Let $$$P = \sum P_i$$$ and $$$S = \sum S_i$$$.
Smallest $$$P$$$ elements should go to prefix of each range and largest $$$S$$$ elements should fo to suffix of each range.

In optimal permutation, we should place $$$1...P$$$ in descending order in prefixes, and we should place $$$P+1....P+S$$$ in descending order in suffixes.

Now, lets do a dp, $$$dp[i][pLen]$$$,
This denotes we have processed first $$$i$$$ ranges so far, smallest pLen elements went to prefix and remaining went to suffix.

Now, we can iterate on value of $$$P_{i+1}$$$ and try to count no of new inversions that will come up.

How to handle elements not present in any range?
We add them in a range of length 1, and take prefix of length 1 or suffix of length 1.

Refer to hints of E1.

Lets merge all intersecting ranges, and look at a group of ranges.

All ranges in this group will have same value of $$$K_i$$$.
This $$$K_i$$$ must be more than or equal to left endpoint of all ranges.
And this $$$K_i$$$ must be less than or equal to right endpoint of all ranges.