Since $$$N$$$ is always even, try visualizing the array as $$$N/2$$$ non-overlapping pairs of adjacent elements.
$$$(A_1,A_2), (A_3,A_4), \dots$$$

If every pair must sum to a multiple of $$$P$$$, what must the total sum $$$M$$$ be a multiple of? Given that numbers must be positive, what is the absolute minimum possible total sum?

To build the array, try repeating a simple pair like $$$(1,P-1)$$$ for most of the array, and put all the remaining required sum into the very last element.

When to print NO:

• Because $$$N$$$ is even, we can split the array into exactly $$$N/2$$$ disjoint pairs. The problem requires every adjacent pair to sum to a multiple of $$$P$$$. Therefore, the sum of the entire array, $$$M$$$, must also be a multiple of $$$P$$$ ($$$M \bmod P = 0$$$).

• Additionally, since the array requires strictly positive integers ($$$A_i \ge 1$$$), the smallest valid sum for any pair is $$$P$$$. With $$$N/2$$$ pairs, the absolute minimum total sum is $$$(N/2) \times P$$$.
  If $$$M \lt (N/2) \times P$$$, it is impossible. Therefore, if either of these conditions fails, print NO.

When to print YES:
If both conditions are met, print YES and construct the array greedily:

• Prefix: Fill the first $$$N-2$$$ positions by alternating $$$1$$$ and $$$P-1$$$: $$$1, P-1, 1, P-1, \dots$$$ Every adjacent pair here sums to exactly $$$P$$$.

• Second to last element: Set $$$A_{N-1} = 1$$$. Since the prefix always ends in $$$P-1$$$, their sum is $$$P-1+1=P$$$, which is valid.

• Final element: Set $$$A_N$$$ to whatever value is needed to make the total array sum exactly $$$M$$$.

Since we already verified that $$$M \ge (N/2)\times P$$$, $$$A_N$$$ will always be a valid positive integer.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

void solve()
{
    int n, m, p;
    cin >> n >> m >> p;
    if ((m % p != 0) || ((m / p) < (n / 2)))
    {
        cout << "NO" << endl;
    }
    else
    {
        cout << "YES" << endl;
        for (int i = 0; i < n - 2; i += 2)
        {
            cout << 1 << " " << p - 1 << " ";
            m -= p;
        }
        cout << 1 << " " << m - 1 << endl;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

Time Complexity: $$$\mathcal{O}(N)$$$
Space Complexity: $$$\mathcal{O}(1)$$$

Notice that the elements of the transformed array $$$A$$$ are powers of $$$2$$$ ($$$A[i] = 2^{b_i}$$$).
Think about the binary representation of numbers. What happens if every element in the array $$$b$$$ is completely distinct?

The sum of any set of strictly distinct powers of $$$2$$$ is uniquely determined by its elements.
Consider the largest element in any two disjoint subsets. If all $$$b_i$$$ are unique, can the subset without the maximum element ever sum up to a value greater than or equal to the maximum element itself?

Try to determine whether two equal-sum subarrays can exist when every value in $$$b$$$ is unique.
What changes if two values of $$$b$$$ are equal?

The problem contains a massive bait in the first example's note, leading you to think about complex prefix sums and combining multiple elements to match a single large power of $$$2$$$. However, the solution is purely based on a fundamental property of powers of $$$2$$$.

Claim: Two non-overlapping equal-sum subarrays exist if and only if there is at least one duplicate element in the array $$$b$$$.

The problem fully reduces to checking whether the array $$$b$$$ contains any duplicate values. This can be done in two ways:

• Sort the array and check adjacent elements.

• Use a Hash Set to detect duplicates.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void solve() {
    int n;
    cin >> n;
    vector<int> b(n);
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    sort(b.begin(), b.end());
    bool has_duplicate = false;
    for (int i = 1; i < n; i++) {
        if (b[i] == b[i - 1]) {
            has_duplicate = true;
            break;
        }
    }
    if (has_duplicate) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Using sorting:
Time Complexity: $$$\mathcal{O}(n \log n)$$$
Space Complexity: $$$\mathcal{O}(1)$$$ if sorting in-place.

Using a Hash Set:
Time Complexity: $$$\mathcal{O}(n)$$$ average.
Space Complexity: $$$\mathcal{O}(n)$$$.

Since rearranging the remaining characters is free, the positions of the characters in $$$s$$$ do not matter.
Think about the problem in terms of the number of $$$0$$$ and $$$1$$$ available in the string.

Suppose the final string $$$t$$$ has length $$$k$$$.
For every character of $$$t$$$, its value must be different from the character at the same position in $$$s$$$.
Ask yourself:
How many $$$0$$$ and $$$1$$$ does $$$t$$$ need, and how many of each do we have available in $$$s$$$? The maximum possible length of $$$t$$$ can then be determined from these two frequencies.

Try matching every character in the original string with an available character of the opposite type. What happens when one of the two types runs out?

The main observation is that free rearrangement removes the importance of ordering. Let:
$$$cnt_0$$$ = number of $$$0$$$s in $$$s$$$
$$$cnt_1$$$ = number of $$$1$$$s in $$$s$$$

If $$$t$$$ has length $$$k$$$, then every $$$0$$$ in $$$t$$$ must occupy a position where $$$s$$$ has a $$$1$$$, and every $$$1$$$ in $$$t$$$ must occupy a position where $$$s$$$ has a $$$0$$$.
Therefore, the number of characters we can keep is limited by the available opposite characters.
The important quantity is the maximum number of characters that can remain after matching each character with an opposite character.
Since every deleted character costs exactly $$$1$$$ coin, once we know the maximum number of characters that can be retained, the answer follows directly.

#include <bits/stdc++.h>
using namespace std;

void solve() {
    string s;
    cin >> s;
    int n = s.size();
    int zeroCount = 0, oneCount = 0;
    for (char c : s) {
        if (c == '0') {
            zeroCount++;
        } else {
            oneCount++;
        }
    }
    for (int i = 0; i < n; i++) {
        if (s[i] == '0') {
            if (oneCount > 0) {
                oneCount--;
            } else {
                cout << n - i << "\n";
                return;
            }
        } else {
            if (zeroCount > 0) {
                zeroCount--;
            } else {
                cout << n - i << "\n";
                return;
            }
        }
    }
    cout << "0\n";
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

We only need to count the number of $$$0$$$ and $$$1$$$.
Time Complexity: $$$\mathcal{O}(n)$$$ per test case
Space Complexity: $$$\mathcal{O}(1)$$$

Don't think of the amplification as changing individual characters. Each character in the original grid is simply replaced by a $$$K \times K$$$ block containing the same character.

For example, if $$$K=2$$$:
X becomes:
XX
XX

For every row of the original grid, we need to:
1. Replace every character with $$$K$$$ copies of that character horizontally.
2. Repeat the resulting row $$$K$$$ times vertically.

Since the original grid has $$$M$$$ rows and $$$N$$$ columns, the final grid will have $$$M \times K$$$ rows and $$$N \times K$$$ columns.

Think about how the position in the amplified grid maps back to the original grid. For a position $$$(i,j)$$$ in the new grid, which original cell does it correspond to?

The key observation is that every original character is expanded independently into a $$$K \times K$$$ block. Suppose the original row is:

For $$$K=2$$$, each character is expanded horizontally:

and this entire row is printed $$$K$$$ times. Therefore, for every input row:

• Build an expanded row by repeating each character $$$K$$$ times.

• Print this expanded row exactly $$$K$$$ times.

This directly produces the required amplified grid.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int height, width;
    int scale;
    cin >> height >> width >> scale;
    vector<string> signal(height);
    for (string &r : signal) {
        cin >> r;
    }
    for (int i = 0; i < scale * height; i++) {
        for (int j = 0; j < scale * width; j++) {
            cout << signal[i / scale][j / scale];
        }
        cout << '\n';
    }
}

The final grid contains $$$(M \times K) \times (N \times K)$$$ characters. Therefore:
Time Complexity: $$$\mathcal{O}(MNK^2)$$$
Space Complexity: $$$\mathcal{O}(NK)$$$ if we store one expanded row.

Don't consider $$$a[i]$$$ and $$$b[i]$$$ independently. If Harry takes a relic, its contribution to the final value $$$H-D$$$ is: $$$+a[i]$$$
If Draco takes it, the contribution is: $$$-b[i]$$$

Think about what happens when one relic is chosen by Harry and another by Draco. Which property of a relic determines how valuable it is to take before another relic?

Suppose you have two relics $$$i$$$ and $$$j$$$, and it is Harry's turn. Compare these two possibilities:

• Harry takes $$$i$$$, then Draco takes $$$j$$$.

• Harry takes $$$j$$$, then Draco takes $$$i$$$.

Write the resulting contribution to $$$H-D$$$ for both orders and compare them.

From the pairwise comparison, try to identify a single value for each relic that determines which relic should come first. Once the sorting criterion is known, simulate the alternating turns.

This is a classic two-player greedy / optimal ordering problem. The important trick is to look at the effect of two consecutive turns together rather than trying to simulate all possible choices. For two relics $$$i$$$ and $$$j$$$:

• If Harry gets $$$i$$$ and Draco gets $$$j$$$, their combined contribution is: $$$a[i]-b[j]$$$

• If Harry gets $$$j$$$ and Draco gets $$$i$$$, their combined contribution is: $$$a[j]-b[i]$$$

Comparing these expressions reveals that the relevant quantity for each relic is: $$$a[i]+b[i]$$$

So the game can be transformed into an ordering problem: determine the order in which the relics should be considered based on this combined value. After finding the correct order:

• Harry takes the relics at his turns.

• Draco takes the relics at his turns.

• Add $$$a[i]$$$ when Harry takes relic $$$i$$$.

• Subtract $$$b[i]$$$ when Draco takes relic $$$i$$$.

#include <algorithm>
#include <cmath>
#include <cstdint>
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pl pair<ll, ll>
#define vl vector<ll>
#define vpl vector<pl>
#define vb vector<bool>
#define vvl vector<vl>
#define vvpl vector<vpl>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define f(i, a, b) for (ll i = (a); i < (b); ++i)
#define rf(i, a, b) for (ll i = (a); i >= (b); --i)
#define each(x, a) for (auto &x : a)
#define uniq(x) x.resize(unique(all(x)) - x.begin())
#define yes cout << "YES\n"
#define no cout << "NO\n";

ll M = (1e+9) + 7;

using namespace std;

bool func(pl &i, pl &j) {
    if (i.first + i.second != j.first + j.second) {
        return i.first + i.second > j.first + j.second;
    } else {
        return i.first > j.first;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    ll t;
    cin >> t;

    while (t--) {
        ll n, ans = 0;

        cin >> n;

        vl a(n);
        vl b(n);
        vvl c(n, vl(3));

        f(i, 0, n) {
            cin >> a[i];
        }

        f(i, 0, n) {
            cin >> b[i];

            c[i][0] = a[i] + b[i];
            c[i][1] = a[i];
            c[i][2] = b[i];
        }

        sort(all(a));

        rf(i, n - 1, 0) {
            if ((n - i) % 2 == 1) {
                ans += c[i][1];
            } else {
                ans -= c[i][2];
            }
        }

        cout << ans << endl;
    }
}

Sorting the relics takes:
Time Complexity: $$$\mathcal{O}(n \log n)$$$

The simulation after sorting takes:
Time Complexity: $$$\mathcal{O}(n)$$$

Therefore, the overall complexity is:
Time Complexity: $$$\mathcal{O}(n \log n)$$$
Space Complexity: $$$\mathcal{O}(n)$$$

The condition says that the sum of the elements in a subarray must be equal to its length. If $$$\sum_{i=l}^{r} a_i = r-l+1$$$
what happens if we write the length as a sum of $$$1$$$?

The length of a subarray is exactly the number of elements in it. Therefore: $$$\sum_{i=l}^{r} a_i = \sum_{i=l}^{r} 1$$$
Can you move everything to one side?

After subtracting $$$1$$$ from every element, the problem becomes: Count the number of subarrays whose sum is exactly $$$0$$$.
How can prefix sums be used to count zero-sum subarrays efficiently?

Key Observation
A subarray $$$[l,r]$$$ is good if $$$\sum_{i=l}^{r} a_i = r-l+1$$$ The right-hand side is simply the number of elements in the subarray, so we can write:

Moving everything to the left gives:

This transformation is the key to the problem.

Transformation
Define a new array $$$b$$$ such that:

Now the original condition becomes: $$$\sum_{i=l}^{r} b_i=0$$$
Therefore, instead of directly checking whether the sum of a subarray of $$$a$$$ equals its length, we simply need to count the number of zero-sum subarrays in $$$b$$$.

For example, if: $$$a=[1,2,0,1]$$$ then:
$$$b=[0,1,-1,0]$$$
Now we only need to count the subarrays of $$$b$$$ whose sum is $$$0$$$.

Using Prefix Sums
Let $$$P_i$$$ denote the sum of the first $$$i$$$ elements of $$$b$$$. For a subarray $$$[l,r]$$$: $$$\sum_{i=l}^{r}b_i=P_r-P_{l-1}$$$
We want this sum to be $$$0$$$, so: $$$P_r-P_{l-1}=0$$$
which means: $$$P_r=P_{l-1}$$$
Therefore, a subarray has sum $$$0$$$ exactly when the prefix sum at its two boundaries is the same.
So, whenever we encounter a prefix sum that has appeared before, every previous occurrence of that prefix sum gives us one new valid subarray.

Counting the Subarrays
We maintain a frequency map containing how many times each prefix sum has appeared.
Initially, the prefix sum is $$$0$$$ before processing any elements. Therefore, we initialize: $$$\text{freq}[0] = 1$$$

For every element:

1. Add the element to the current prefix sum.

2. Add $$$\text{freq}[\text{prefix}]$$$ to the answer.

3. Increment $$$\text{freq}[\text{prefix}]$$$

Why does this work?
Suppose the current prefix sum is $$$x$$$ and it has appeared $$$k$$$ times before. Each previous occurrence of $$$x$$$ gives a different starting position for a zero-sum subarray ending at the current position. Therefore, we can add $$$k$$$ directly to the answer.

Correctness
Consider any subarray $$$[l,r]$$$. It is good in the original array if and only if: $$$\sum_{i=l}^{r}a_i=r-l+1$$$
This is equivalent to: $$$\sum_{i=l}^{r}(a_i-1)=0$$$
After defining $$$b_i=a_i-1$$$, this means: $$$\sum_{i=l}^{r}b_i=0$$$
Using prefix sums: $$$P_r=P_{l-1}$$$

Our frequency map counts exactly the number of previous positions having the same prefix sum. Thus, every good subarray is counted exactly once, and no invalid subarray is counted.
Therefore, the algorithm correctly computes the number of good subarrays.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++)
            cin >> a[i];

        vector<int> cnt(9 * n + 2, 0);
        int cur = 0;
        // Empty prefix
        cnt[n] = 1;
        long long ans = 0;
        for (int i = 0; i < n; i++) {
            cur += a[i] - 1;
            ans += cnt[cur + n];
            cnt[cur + n]++;
        }
        cout << ans << '\n';
    }
    return 0;
}

Each element is processed exactly once.

Using a hash map:
Time Complexity: $$$\mathcal{O}(N)$$$ average per test case
Space Complexity: $$$\mathcal{O}(N)$$$
Since $$$\sum N \le 2\cdot10^5$$$, this easily fits within the constraints.

Alternatively, using an ordered map gives:
Time Complexity: $$$\mathcal{O}(N\log N)$$$
Space Complexity: $$$\mathcal{O}(N)$$$

Think about what happens if you pick a random starting node and walk as far as possible. Where do you end up? Does that destination have a special structural role in the tree?

Every tree has a diameter — the longest path between any two nodes. Let the endpoints of this diameter be $$$A$$$ and $$$B$$$.
If you are standing at an arbitrary node $$$v$$$, how does the farthest possible destination relate to $$$A$$$ and $$$B$$$?

With up to $$$10^5$$$ queries, running a complete BFS or DFS for every query is too slow.
Can we precompute distances from a small number of important nodes so that every query can be answered in constant time?

Core Idea
The problem asks for the maximum distance from a given node $$$v$$$ to any other node in the tree.
Running BFS or DFS independently for every query would take $$$\mathcal{O}(nq)$$$ time, which is too large.

The key observation is based on the diameter of a tree.
Let the two endpoints of the diameter be $$$A$$$ and $$$B$$$. For every node $$$v$$$, at least one of these two endpoints is a farthest node from $$$v$$$. Therefore:

Claim 1 — Finding a Diameter Endpoint
Start from any node, for example node $$$1$$$, and find the farthest node from it. This node is guaranteed to be one endpoint of the tree's diameter. Let this node be $$$A$$$.

Claim 2 — Finding the Other Endpoint
Now run BFS or DFS starting from $$$A$$$. The farthest node from $$$A$$$ is the other endpoint of the diameter. Let this node be $$$B$$$. During this traversal, also store the distance from $$$A$$$ to every node in an array $$$\text{dist}_A$$$.

Claim 3 — Farthest Node Property
For every node $$$v$$$, one of the diameter endpoints $$$A$$$ or $$$B$$$ is a farthest node from $$$v$$$. Therefore:

This allows us to answer every query without performing another traversal.

Proof
Let $$$A$$$ and $$$B$$$ be the endpoints of the tree's diameter. Consider an arbitrary node $$$v$$$ and let $$$u$$$ be a farthest node from $$$v$$$. In a tree, paths are unique. The diameter endpoints capture the maximum extent of the tree, and the eccentricity of any node is determined by its distance to one of these endpoints. Hence:

Therefore, the maximum distance from $$$v$$$ can always be obtained by checking only $$$A$$$ and $$$B$$$.

Step-by-Step Approach

1. Find $$$A$$$ Run BFS/DFS from node $$$1$$$ and find the farthest node. Call it $$$A$$$.

2. Find $$$B$$$ and $$$\text{dist}_A$$$ Run BFS/DFS from $$$A$$$. The farthest node is $$$B$$$. Store the distance from $$$A$$$ to every node in $$$\text{dist}_A$$$.

3. Calculate $$$\text{dist}_B$$$ Run BFS/DFS from $$$B$$$ and store the distance from $$$B$$$ to every node in $$$\text{dist}_B$$$.

4. Answer the queries For every queried node $$$v$$$: $$$\text{answer}=\max(\text{dist}_A[v],\text{dist}_B[v])$$$, Each query is now answered in $$$\mathcal{O}(1)$$$.

We perform three BFS/DFS traversals, each taking $$$\mathcal{O}(n)$$$ time. Each query is answered in $$$\mathcal{O}(1)$$$ time.

Time Complexity: $$$\mathcal{O}(n+q)$$$
Space Complexity: $$$\mathcal{O}(n)$$$