1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Palindromic Indices
Contest: Codeforces Round 793 (Div. 2)
Difficulty rating: 800
Tags: greedy, strings

You are given a palindromic string $$$s$$$ of length $$$n$$$.

You have to count the number of indices $$$i$$$ $$$(1 \le i \le n)$$$ such that the string after removing $$$s_i$$$ from $$$s$$$ still remains a palindrome.

For example, consider $$$s$$$ = "aba"

1. If we remove $$$s_1$$$ from $$$s$$$, the string becomes "ba" which is not a palindrome.
2. If we remove $$$s_2$$$ from $$$s$$$, the string becomes "aa" which is a palindrome.
3. If we remove $$$s_3$$$ from $$$s$$$, the string becomes "ab" which is not a palindrome.

A palindrome is a string that reads the same backward as forward. For example, "abba", "a", "fef" are palindromes whereas "codeforces", "acd", "xy" are not.

Input format:
The input consists of multiple test cases. The first line of the input contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^3)$$$  — the number of test cases. Description of the test cases follows.

The first line of each testcase contains a single integer $$$n$$$ $$$(2 \leq n \leq 10^5)$$$  — the length of string $$$s$$$.

The second line of each test case contains a string $$$s$$$ consisting of lowercase English letters. It is guaranteed that $$$s$$$ is a palindrome.

It is guaranteed that sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output a single integer  — the number of indices $$$i$$$ $$$(1 \le i \le n)$$$ such that the string after removing $$$s_i$$$ from $$$s$$$ still remains a palindrome.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
The first test case is described in the statement.

In the second test case, the indices $$$i$$$ that result in palindrome after removing $$$s_i$$$ are $$$3, 4, 5, 6$$$. Hence the answer is $$$4$$$.

In the third test case, removal of any of the indices results in "d" which is a palindrome. Hence the answer is $$$2$$$.

Example input:
3
3
aba
8
acaaaaca
2
dd

Example output:
1
4
2

Editorial:
Let's remove index $$$i$$$ from $$$s$$$ and check when the resulting string will be a palindrome. The prefix of length $$$i-1$$$ already matches with suffix, so we need to check is $$$t = s[i + 1 \ldots n - i + 1]$$$ palindrome. The initial string is palindrome, so $$$s_j = s_{n - j + 1}$$$ for $$$1\leq j \leq n$$$.
For $$$t$$$ to be palidrome, $$$s_{i + 1} = s_{n - i + 1}, s_{i + 2} = s_{n - i}$$$ and so on. Note that $$$s_i = {n - i + 1}$$$, hence $$$s_i = s_{i + 1}$$$ and similarly $$$s_{i + 1} = s_{n - i} = s_{i + 2}$$$. Hence we can see that $$$s_i = s_{i + 1} \ldots = s_{n - i + 1}$$$. So answer is equal to number of equal characters in middle of string. Which can be calculated in $$$\mathcal{O(n)}$$$.
Sereja and Coat Rack
Contest: Codeforces Round 215 (Div. 2)
Difficulty rating: 1000
Tags: implementation

Sereja owns a restaurant for n people. The restaurant hall has a coat rack with n hooks. Each restaurant visitor can use a hook to hang his clothes on it. Using the i-th hook costs ai rubles. Only one person can hang clothes on one hook.

Tonight Sereja expects m guests in the restaurant. Naturally, each guest wants to hang his clothes on an available hook with minimum price (if there are multiple such hooks, he chooses any of them). However if the moment a guest arrives the rack has no available hooks, Sereja must pay a d ruble fine to the guest.

Help Sereja find out the profit in rubles (possibly negative) that he will get tonight. You can assume that before the guests arrive, all hooks on the rack are available, all guests come at different time, nobody besides the m guests is visiting Sereja's restaurant tonight.

Input format:
The first line contains two integers n and d (1 ≤ n, d ≤ 100). The next line contains integers a1, a2, ..., an (1 ≤ ai ≤ 100). The third line contains integer m (1 ≤ m ≤ 100).

Output format:
In a single line print a single integer — the answer to the problem.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test both hooks will be used, so Sereja gets 1 + 2 = 3 rubles.

In the second test both hooks will be used but Sereja pays a fine 8 times, so the answer is 3 - 8 =  - 5.

Example input:
2 1
2 1
2

Example output:
3

Example input:
2 1
2 1
10

Example output:
-5

Editorial:
Sereja and Suffixes
Contest: Codeforces Round 215 (Div. 2)
Difficulty rating: 1100
Tags: data structures, dp

Sereja has an array a, consisting of n integers a1, a2, ..., an. The boy cannot sit and do nothing, he decided to study an array. Sereja took a piece of paper and wrote out m integers l1, l2, ..., lm (1 ≤ li ≤ n). For each number li he wants to know how many distinct numbers are staying on the positions li, li + 1, ..., n. Formally, he want to find the number of distinct numbers among ali, ali + 1, ..., an.?

Sereja wrote out the necessary array elements but the array was so large and the boy was so pressed for time. Help him, find the answer for the described question for each li.

Input format:
The first line contains two integers n and m (1 ≤ n, m ≤ 105). The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 105) — the array elements.

Next m lines contain integers l1, l2, ..., lm. The i-th line contains integer li (1 ≤ li ≤ n).

Output format:
Print m lines — on the i-th line print the answer to the number li.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
10 10
1 2 3 4 1 2 3 4 100000 99999
1
2
3
4
5
6
7
8
9
10

Example output:
6
6
6
6
6
5
4
3
2
1

Editorial:
Destroyer
Contest: Codeforces Round 880 (Div. 2)
Difficulty rating: 800
Tags: implementation, sortings

John is a lead programmer on a destroyer belonging to the space navy of the Confederacy of Independent Operating Systems. One of his tasks is checking if the electronic brains of robots were damaged during battles.

A standard test is to order the robots to form one or several lines, in each line the robots should stand one after another. After that, each robot reports the number of robots standing in front of it in its line.

An example of robots' arrangement (the front of the lines is on the left). The robots report the numbers above.

The $$$i$$$-th robot reported number $$$l_i$$$. Unfortunately, John does not know which line each robot stands in, and can't check the reported numbers. Please determine if it is possible to form the lines in such a way that all reported numbers are correct, or not.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$), denoting the number of test cases.

The first line in each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the number of robots.

The second line in each test case contains $$$n$$$ integers $$$l_1, l_2, \ldots, l_n$$$ ($$$0 \leq l_i < 100$$$), $$$l_i$$$ is equal to the number of robots in front of the $$$i$$$-th robot in its line.

The sum of $$$n$$$ over all test cases won't exceed $$$200$$$.

Output format:
For each test case, output "YES", if there exists a robot arrangement consistent with robots' reports. Otherwise, output "NO".

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
Example arrangement consistent with robot statements from the first example test case:

Example arrangement consistent with robot statements from the second example is shown in the statement.

In the third test case, the third robot claims that there are two machines in front of it. In such a case, the robot directly in front of it would have one machine in front. No robot claims that, so there is no valid arrangement.

Example input:
5
6
0 1 2 0 1 0
9
0 0 0 0 1 1 1 2 2
3
0 0 2
1
99
5
0 1 2 3 4

Example output:
YES
YES
NO
NO
YES

Editorial:
We can simplify the statement to the following — can we divide the input sequence into multiple arithmetic sequences starting with $$$0$$$ and a common difference equal to $$$1$$$?
Note that for each such arithmetic sequence, if a number $$$x > 0$$$ belongs to it, then $$$x - 1$$$ must also be included in it. Thus, if we denote $$$cnt_x$$$ as the number of occurrences of $$$x$$$ in the input, we must have $$$cnt_x \geq cnt_{x + 1}$$$ for each $$$x \geq 0$$$. We can note that if such a condition is fulfilled, we can always divide the input into described arithmetic sequences.
We can implement it straightforwardly in $$$\mathcal{O}(N + L)$$$, where $$$L$$$ is the maximum value in the input.
Is it stated?
Contest: April Fools Day Contest 2024
Tags: *special, strings

Input format:
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of testcases.

The following $$$t$$$ lines each contain a string of length at most $$$100$$$ consisting of lowercase English letters.

Output format:
For each test case, output "YES" or "NO", denoting the answer.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
10
is
it
stated
submit
ac
accepted
wa
wronganswer
tle
timelimitexceeded

Example output:
NO
YES
NO
YES
NO
NO
NO
NO
NO
YES

Editorial:
You just need to check if there is a substring it in the string. (That is, the question is asking, "is it stated?")
They Have Fooled
Contest: April Fools Day Contest 2024
Tags: *special, brute force, schedules

Input format:
The first line contains one integer $$$n$$$ ($$$0 \leq n \leq 12$$$).

Output format:
One integer — the answer.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
0

Example output:
10

Example input:
1

Example output:
10

Editorial:
Sweep Line
Contest: April Fools Day Contest 2024
Tags: *special, combinatorics, games, math

Input format:
The first line contains one integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the length of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 2$$$) — the array $$$a$$$.

Output format:
Output a single integer — the number of solutions, modulo $$$20240401$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first sample, the array looks like this:

$$$ \color{blue}{1} $$$$$$ \color{blue}{1} $$$$$$ \color{darkgreen}{2} $$$$$$ \color{blue}{1} $$$$$$ \color{blue}{1} $$$$$$ \color{darkgreen}{2} $$$$$$ \color{gray}{0} $$$

Obviously, the answer here is $$$1 \pmod{20240401}$$$.

In the second sample, the array looks like this:

$$$ \color{blue}{1} $$$$$$ \color{blue}{1} $$$$$$ \color{darkgreen}{2} $$$$$$ \color{blue}{1} $$$$$$ \color{blue}{1} $$$$$$ \color{blue}{1} $$$$$$ \color{gray}{0} $$$

I do not know why the answer here is $$$2 \pmod{20240401}$$$, I had to take a guess.

In the third sample, the array looks like this:

$$$ \color{gray}{0} $$$$$$ \color{blue}{1} $$$$$$ \color{darkgreen}{2} $$$$$$ \color{blue}{1} $$$$$$ \color{blue}{1} $$$$$$ \color{blue}{1} $$$$$$ \color{gray}{0} $$$

If the answer here is not $$$0 \pmod{20240401}$$$, I am literally going to explode.

Example input:
7
1 1 2 1 1 2 0

Example output:
1

Example input:
7
1 1 2 1 1 1 0

Example output:
2

Editorial:
Grid
Contest: April Fools Day Contest 2024
Tags: *special, brute force

Input format:
The input contains $$$21$$$ lines, each containing $$$21$$$ characters $$$\texttt{0}$$$ or $$$\texttt{1}$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
111111101011101111111
100000100011001000001
101110101101001011101
101110101100101011101
101110101001001011101
100000100111101000001
111111101010101111111
000000000001100000000
111100101111110011101
000111010101100110101
111101101101001000011
001001000001000011000
111101110000111001011
000000001001001111100
111111100001101010000
100000100010010100111
101110100110110011100
101110101100000100010
101110101010110000100
100000101000011001001
111111101011111111100

Example output:
12

Editorial:
Mathematician Takeover
Contest: April Fools Day Contest 2024
Tags: *special, binary search, dfs and similar, math

A mathematician grabbed my computer as I was preparing this problem, deleted the statement, and changed the samples to fit his liking. The model solution and input/output format are still correct, but the samples are wrong.

I've partially fixed the problem so that when you submit, it will be tested against the correct version of the problem. However, I can't fix the samples below. As a computer scientist, can you solve the correct problem?

Input format:
The only line of input contains a real number $$$x$$$ ($$$1 \leq x \leq 100$$$), given to exactly three decimal places.

Output format:
Output one real number — the answer. Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-4}$$$. Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a-b|}{\max(1,|b|)} \le 10^{-4}$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
1.234

Example output:
0.21026

Example input:
4.113

Example output:
1.41415

Editorial:
Palindrome
Contest: April Fools Day Contest 2024
Tags: *special, implementation, strings

A palindrome is a string that reads the same in both directions, for example z, uwu, or moom.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of testcases.

The following $$$t$$$ lines each contain a string of length at most $$$100$$$ consisting of lowercase English letters.

Output format:
For each test case, output "YES" or "NO", denoting the answer.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Example input:
8
ac
tle
radar
racecar
php
atcoder
codeforces
steam

Example output:
NO
NO
YES
YES
NO
NO
YES
YES

Example input:
2
a
z

Example output:
NO
YES

Editorial:
Help, what does it mean to be "Based"
Contest: April Fools Day Contest 2024
Tags: *special, brute force, constructive algorithms, expression parsing, implementation, sortings

Input format:
Sup, gimme a single integer $$$x$$$ ($$$1 \le x \le 4$$$) homie uwu :3

Output format:
If $$$x = 1$$$, spit out some based code that, like when ya feed it two integers $$$a$$$ and $$$b$$$, it hands over their sum.

If $$$x = 2$$$, slap some based code that takes an integer $$$a$$$ and returns its absolute value like magic, no cap.

If $$$x = 3$$$, check this out: blaze some based code that grabs an integer $$$n$$$ ($$$1 \le n \le 50$$$) and an array $$$a$$$ of $$$n$$$ distinct integers, then flexes the maximum value real quick.

If $$$x = 4$$$, toss me some based code that snatches an integer $$$n$$$ ($$$1 \le n \le 50$$$), an array $$$a$$$ of $$$n$$$ distinct integers and an integer $$$k$$$ ($$$1 \le k \le n$$$), then nails down that $$$k$$$-th largest value in the array. Get it, fam!

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
Slide into the "My Submissions" page and vibe check ur code by clicking on its ID. You'll see just how based or cringe it is.

Example input:
1

Example output:
yoink a
yoink b
*slaps a on top of b*
yeet b
go touch some grass

Example input:
2

Example output:
yoink a
bruh b is lowkey just 0
rip this b fell off by a
vibe check a ratios b
simp for 7
bruh a is lowkey just b
yeet a
go touch some grass

Editorial:
Distance and Axis
Contest: Codeforces Round 665 (Div. 2)
Difficulty rating: 900
Tags: constructive algorithms, math

We have a point $$$A$$$ with coordinate $$$x = n$$$ on $$$OX$$$-axis. We'd like to find an integer point $$$B$$$ (also on $$$OX$$$-axis), such that the absolute difference between the distance from $$$O$$$ to $$$B$$$ and the distance from $$$A$$$ to $$$B$$$ is equal to $$$k$$$.

The description of the first test case.

Since sometimes it's impossible to find such point $$$B$$$, we can, in one step, increase or decrease the coordinate of $$$A$$$ by $$$1$$$. What is the minimum number of steps we should do to make such point $$$B$$$ exist?

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 6000$$$) — the number of test cases.

The only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$0 \le n, k \le 10^6$$$) — the initial position of point $$$A$$$ and desirable absolute difference.

Output format:
For each test case, print the minimum number of steps to make point $$$B$$$ exist.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case (picture above), if we set the coordinate of $$$B$$$ as $$$2$$$ then the absolute difference will be equal to $$$|(2 - 0) - (4 - 2)| = 0$$$ and we don't have to move $$$A$$$. So the answer is $$$0$$$.

In the second test case, we can increase the coordinate of $$$A$$$ by $$$3$$$ and set the coordinate of $$$B$$$ as $$$0$$$ or $$$8$$$. The absolute difference will be equal to $$$|8 - 0| = 8$$$, so the answer is $$$3$$$.

Example input:
6
4 0
5 8
0 1000000
0 0
1 0
1000000 1000000

Example output:
0
3
1000000
0
1
0

Editorial:
If $$$n$$$ is less than $$$k$$$, we have to move $$$A$$$ to coordinate $$$k$$$, and set the coordinate of $$$B$$$ as $$$0$$$ or $$$k$$$. So the answer is $$$k - n$$$.
If $$$n$$$ is not less than $$$k$$$, let's define the coordinate of $$$B$$$ as $$$m$$$($$$m \times 2 \le n$$$). By the condition in the problem, the difference between ($$$m - 0$$$) and ($$$n - m$$$) should be equal to $$$k$$$. That is, $$$(n - m) - (m - 0)$$$ is $$$k$$$, and summarizing the formula, $$$m = (n - k) / 2$$$. Because the coordinate of $$$B$$$ is integer, if the parity of $$$n$$$ and $$$k$$$ is same the answer is $$$0$$$, otherwise the answer is $$$1$$$(If we increase the coordinate of $$$A$$$ by $$$1$$$, m becomes integer).
Time complexity : $$$O(1)$$$
Ternary Sequence
Contest: Codeforces Round 665 (Div. 2)
Difficulty rating: 1100
Tags: constructive algorithms, greedy, math

You are given two sequences $$$a_1, a_2, \dots, a_n$$$ and $$$b_1, b_2, \dots, b_n$$$. Each element of both sequences is either $$$0$$$, $$$1$$$ or $$$2$$$. The number of elements $$$0$$$, $$$1$$$, $$$2$$$ in the sequence $$$a$$$ is $$$x_1$$$, $$$y_1$$$, $$$z_1$$$ respectively, and the number of elements $$$0$$$, $$$1$$$, $$$2$$$ in the sequence $$$b$$$ is $$$x_2$$$, $$$y_2$$$, $$$z_2$$$ respectively.

You can rearrange the elements in both sequences $$$a$$$ and $$$b$$$ however you like. After that, let's define a sequence $$$c$$$ as follows:

$$$c_i = \begin{cases} a_i b_i & \mbox{if }a_i > b_i \\ 0 & \mbox{if }a_i = b_i \\ -a_i b_i & \mbox{if }a_i < b_i \end{cases}$$$

You'd like to make $$$\sum_{i=1}^n c_i$$$ (the sum of all elements of the sequence $$$c$$$) as large as possible. What is the maximum possible sum?

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each test case consists of two lines. The first line of each test case contains three integers $$$x_1$$$, $$$y_1$$$, $$$z_1$$$ ($$$0 \le x_1, y_1, z_1 \le 10^8$$$) — the number of $$$0$$$-s, $$$1$$$-s and $$$2$$$-s in the sequence $$$a$$$.

The second line of each test case also contains three integers $$$x_2$$$, $$$y_2$$$, $$$z_2$$$ ($$$0 \le x_2, y_2, z_2 \le 10^8$$$; $$$x_1 + y_1 + z_1 = x_2 + y_2 + z_2 > 0$$$) — the number of $$$0$$$-s, $$$1$$$-s and $$$2$$$-s in the sequence $$$b$$$.

Output format:
For each test case, print the maximum possible sum of the sequence $$$c$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample, one of the optimal solutions is:

$$$a = \{2, 0, 1, 1, 0, 2, 1\}$$$

$$$b = \{1, 0, 1, 0, 2, 1, 0\}$$$

$$$c = \{2, 0, 0, 0, 0, 2, 0\}$$$

In the second sample, one of the optimal solutions is:

$$$a = \{0, 2, 0, 0, 0\}$$$

$$$b = \{1, 1, 0, 1, 0\}$$$

$$$c = \{0, 2, 0, 0, 0\}$$$

In the third sample, the only possible solution is:

$$$a = \{2\}$$$

$$$b = \{2\}$$$

$$$c = \{0\}$$$

Example input:
3
2 3 2
3 3 1
4 0 1
2 3 0
0 0 1
0 0 1

Example output:
4
2
0

Editorial:
We can find the kind of the value of $$$c_i$$$ is three $$$\left(-2, 0, 2\right)$$$. And $$$c_i$$$ is $$$-2$$$ only if $$$a_i$$$ is $$$1$$$ and $$$b_i$$$ is $$$2$$$, and $$$c_i$$$ is $$$2$$$ only if $$$a_i$$$ is $$$2$$$ and $$$b_i$$$ is $$$1$$$. Otherwise $$$c_i$$$ is $$$0$$$. So we have to make ($$$a_i, b_i$$$) pair ($$$1, 2$$$) as little as possible, and pair ($$$2, 1$$$) as much as possible. To do this, first we can make ($$$1, 0$$$) pair, ($$$0, 2$$$) pair, and ($$$2, 1$$$) pair as much as possible. After that, pairing the remaining values doesn't affect the sum of $$$c_i$$$. (It $$$a_i$$$ in which value is $$$1$$$ and $$$b_i$$$ in which value is $$$2$$$ are all left, we have to pair them although the sum decreases.)
Time complexity : $$$O(1)$$$
Mere Array
Contest: Codeforces Round 665 (Div. 2)
Difficulty rating: 1300
Tags: constructive algorithms, math, number theory, sortings

You are given an array $$$a_1, a_2, \dots, a_n$$$ where all $$$a_i$$$ are integers and greater than $$$0$$$.

In one operation, you can choose two different indices $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le n$$$). If $$$gcd(a_i, a_j)$$$ is equal to the minimum element of the whole array $$$a$$$, you can swap $$$a_i$$$ and $$$a_j$$$. $$$gcd(x, y)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$.

Now you'd like to make $$$a$$$ non-decreasing using the operation any number of times (possibly zero). Determine if you can do this.

An array $$$a$$$ is non-decreasing if and only if $$$a_1 \le a_2 \le \ldots \le a_n$$$.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of array $$$a$$$.

The second line of each test case contains $$$n$$$ positive integers $$$a_1, a_2, \ldots a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the array itself.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$.

Output format:
For each test case, output "YES" if it is possible to make the array $$$a$$$ non-decreasing using the described operation, or "NO" if it is impossible to do so.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first and third sample, the array is already non-decreasing.

In the second sample, we can swap $$$a_1$$$ and $$$a_3$$$ first, and swap $$$a_1$$$ and $$$a_5$$$ second to make the array non-decreasing.

In the forth sample, we cannot the array non-decreasing using the operation.

Example input:
4
1
8
6
4 3 6 6 2 9
4
4 5 6 7
5
7 5 2 2 4

Example output:
YES
YES
YES
NO

Editorial:
Let's define the minimum element of $$$a$$$ as $$$m$$$. We can find the position of the elements which is not divisible by $$$m$$$ cannot be changed because these elements don't have $$$m$$$ as factor. But we can rearrange elements divisible by $$$m$$$ whatever we want in the following way:
$$$\bullet$$$ Let's suppose $$$m$$$ = $$$a_x$$$, and there is two elements $$$a_y$$$, $$$a_z$$$ in which $$$x$$$, $$$y$$$, $$$z$$$ are all different. Swap($$$a_x$$$, $$$a_y$$$), swap($$$a_y$$$, $$$a_z$$$), and swap($$$a_z$$$, $$$a_x$$$). Then only $$$a_y$$$ and $$$a_z$$$ are swapped from the initial state. Repeat this process.
So we can rearrange elements divisible by $$$m$$$ in non-descending order. After that if whole array is non-descending the answer is $$$YES$$$, otherwise $$$NO$$$.
Time complexity : $$$O(n \log n)$$$