Let’s start with $$$p = [1, 2, 3, …, n]$$$. For this $$$p$$$, $$$f(p) = 0$$$.

Let’s move $$$n$$$ to the beginning one position at a time. It’s easy to see that we increase the answer by $$$2$$$ at each step.

Now, let’s move $$$n - 1$$$ to position $$$2$$$, then $$$n - 2$$$ to position $$$3$$$, and so on, until we reach $$$p = [n, n - 1, …, 2, 1]$$$.
For this $$$p$$$, $$$f(p) = \lfloor \frac{n^2}{2} \rfloor$$$.

While doing this, we obtained every even value from $$$0$$$ to $$$\lfloor \frac{n^2}{2} \rfloor$$$, since we were adding $$$+2$$$ at each step.

Let’s prove that we can’t get any other values.

First of all, it’s easy to see that we can’t obtain a value less than $$$0$$$ or greater than $$$\lfloor \frac{n^2}{2} \rfloor$$$.

Second, we can only obtain even values, because each swap changes the answer by an even number.

So the answer is $$$\lfloor \frac{n^2}{4} \rfloor + 1$$$

Time complexity : $$$\text{O}(1)$$$.

#include <iostream>
#include <vector>
using namespace std;
typedef long long int ll;
#define SPEEDY std::ios_base::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);
#define forn(i, n) for (ll i = 0; i < ll(n); ++i)

void solution(){
    ll n;cin>>n;
    ll k=n/2;
    if (n%2){cout<<k*(k+1)+1;return;}
    cout<<k*k+1;
}

int main() {
    SPEEDY;
    int t; cin>>t;
    while (t--){
        solution();
        cout << '\n';
    } return 0;
}

Let $$$x \gt 1$$$, and let $$$c$$$ denote the number of 1-bits in its binary representation. Clearly, when $$$n \le c$$$, it is optimal to simply distribute distinct powers of two across the elements of the array, resulting in the minimum achievable sum of $$$x$$$. If, however, $$$n \gt c$$$, then it is obviously beneficial to add only ones to the extra $$$n - c$$$ elements. In the case where $$$n - c$$$ is odd, we will also need to add one more one to one of the $$$c$$$ blocks with powers of two so that the $$$\text{XOR}$$$ of all ones equals $$$x$$$ $$$\text{mod}$$$ $$$2$$$.

If $$$x = 1$$$, then for odd $$$n$$$ we can clearly just fill all array elements with ones. Otherwise, we need to use the pair $$$[2, 3]$$$, whose $$$\text{XOR}$$$ is $$$1$$$, resulting in the minimum score of $$$n + 3$$$.

In the remaining case of $$$x = 0$$$, the situation is nearly identical to the previous one, with the exception that no valid example exists for $$$n = 1$$$ (this is the only case with an answer of $$$-1$$$). So for even $$$n$$$, the answer is simply $$$n$$$, and otherwise it’s $$$n + 3$$$ (since we use the triple $$$1 \oplus 2 \oplus 3 = 0$$$).

The time complexity is $$$\text{O}(1)$$$ per test.

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

void solution(){
    int n,x;cin>>n>>x;
    int bits=__builtin_popcountll(x);
    if (n<=bits){cout<<x;return;}
    if ((n-bits)%2==0)cout<<x+n-bits;
    else{
        if (x>1){cout<<x+n-bits+1;return;}
        if (x==1){cout<<n+3;return;}
        else{
            if (n==1){cout<<-1;return;}
            else cout<<n+3;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t=1; 
    cin>>t;
    while (t--){
        solution();
        cout << '\n';
    } return 0;
}

Note that consecutive buttons with the same weight do not affect the result, so we will keep only one of them in such sequences.

In the resulting array, we find peaks (local maxima — elements that are strictly greater than both of their neighbors). The number of such peaks is the answer, because:

— Each peak is separated from others by smaller elements. Therefore, the only way to reach a peak is by creating a clone there.

— If a button was visited, we can return to it.

— Any element other than a peak can be reached from a larger neighbor, since we have already visited it. Thus, creating clones in all other elements is not necessary.

Complexity: $$$\text{O}(n)$$$

#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
    int tt = 1;
    cin >> tt;
    while(tt--){
        int n; cin >> n;
        vector<int> a;
        a.push_back(-1e9);
        for (int i = 0; i < n; i++){
            int x; cin >> x;
            if (a.back() == x);
            else a.push_back(x);
        }
        a.push_back(-1e9);
        
        int ans = 0;
        for (int i = 1; i < a.size() - 1; i++) 
            if (a[i - 1] < a[i] && a[i] > a[i + 1]) ans++;
 
        cout << ans << endl;
    }
}

Let $$$k = 4$$$ and the following array is guessed:

[  2   4   3   1   2   4   3   1   2   1   3   2   4   1   3   2   4   1  ]

For clarity, let's divide it into groups of $$$k$$$ elements:

[  2   4   3   1  ] [  2   4   3   1  ] [  2   1   3   2  ] [  4   1   3   2  ] [  4   1  ]

By statement, the lengths of the left and right sides are at least $$$k$$$. Let's request the left $$$k$$$ and right $$$k$$$ elements. We will mark all the elements of the left array in red, and all the elements of the right array in blue:

[  2   4   3   1  ] [  2   4   3   1  ] [  2   1   3   2  ] [  4   1   3   2  ] [  4   1  ]

Let's add two numbers to our array on the right (for clarity of permutations):

[  2   4   3   1  ] [  2   4   3   1  ] [  2   1   3   2  ] [  4   1   3   2  ] [  4   1   3   2  ]

We got the permutations in a "normalized" form: $$$[2, 4, 3, 1]$$$ and $$$[4, 1, 3, 2]$$$. Let's take any position where the elements in the permutations differ. Let it be the second position. Note all the elements at the selected positions in the guessed array:

[  2   4   3   1  ] [  2   4   3   1  ] [  2   1   3   2  ] [  4   1   3   2  ] [  4   1   3   2  ]

Among them, we find boundary elements via binary search for $$$\log\frac{n}{k}$$$ queries:

[  2   4   3   1  ] [  2   4   3   1  ] [  2   1   3   2  ] [  4   1   3   2  ] [  4   1   3   2  ]

Next, consider the segment between these boundary elements:

[  2   4   3   1  ] [  2   4   3   1  ] [  2   1   3   2  ] [  4   1   3   2  ] [  4   1   3   2  ]

We are not interested in positions that match in both permutations (in our case, this is only the third position). Let's discard the elements in these positions:

[  2   4   3   1  ] [  2   4   3   1  ] [  2   1   3   2  ] [  4   1   3   2  ] [  4   1   3   2  ]

Using binary search, we find the boundary elements for $$$\log k$$$ queries:

[  2   4   3   1  ] [  2   4   3   1  ] [  2   1   3   2  ] [  4   1   3   2  ] [  4   1   3   2  ]

If there are "no-man's land" between the boundary elements, then there is no single solution and we output $$$-1$$$. In our case, there are no such elements, the problem is solved:

[  2   4   3   1  ] [  2   4   3   1  ] [  2   1   3   2  ] [  4   1   3   2  ] [  4   1  ]

Total complexity: $$$2k + \log\frac{n}{k} + \log k$$$ queries.

#include <cstdio>
#include <cstdlib>
#define MIN(X, Y) (((X) < (Y)) ? (X) : (Y))
#define MAX(X, Y) (((X) > (Y)) ? (X) : (Y))
typedef long long l;

l a[55], b[55], ui[55];

l ask(l v) {
    printf("? %lld\n", v + 1);
    fflush(stdout);
    l t; scanf("%lld", &t);
    return t;
}

void noans() {
    printf("! -1\n");
    fflush(stdout);
}

void ans(l a, l b) {
    printf("! %lld %lld\n", a, b);
    fflush(stdout);
}

void solve() {
    l n, k; scanf("%lld %lld", &n, &k);

    for (l i = 0; i < k; ++i) a[i] = ask(i);
    for (l i = n - k; i < n; ++i) b[i % k] = ask(i);
	
    l uc = 0;
    for (l i = 0; i < k; ++i) if (a[i] != b[i]) ui[uc++] = i;
    
    if (!uc) {
        if (n == k * 2) ans(k, k);
        else noans();
        return;
    }
    
    l le = ui[0], ri = ui[0] + (n - 1) / k * k;
    while (le + k != ri) {
        l mid = le + (ri - le) / k / 2 * k;
        if (ask(mid) == a[ui[0]]) le = mid;
        else ri = mid;
    }
    
    l lee = 0, rii = uc;
    while (lee + 1 != rii) {
        l mid = (lee + rii) / 2;
        if (ask(le - ui[0] + ui[mid]) == a[ui[mid]]) lee = mid;
        else rii = mid;
    }
    
    l pos1 = MAX(le - ui[0] + ui[lee], k - 1);
    l pos2 = MIN(le - ui[0] + ((rii == uc) ? (ui[0] + k) : ui[rii]), n - k);
    
    if (pos1 + 1 != pos2) { noans(); return; }
    ans(pos2, n - pos2);
}

int main() {
    l t; scanf("%lld", &t);
    while (t--) solve();
}

Let’s assume we have already removed one of the edges from the original tree. Then, we are left with a tree containing an even number of vertices, namely $$$n - 1$$$.
Note that the maximum possible sum of distances between same-colored balls in this tree will be achieved if, for every edge, all vertices in its smaller subtree are of different colors. In that case, the edge will contribute the maximum possible number of times to the answer — specifically, $$$\min(a, b)$$$, where $$$a$$$ and $$$b$$$ are the sizes of the subtrees connected by this edge (since, obviously, no more paths can pass through this edge).
Great — now let’s root our tree at its centroid, which is a vertex that splits the tree into subtrees whose sizes do not exceed half of the total size. It can be proven that such a vertex always exists in any tree (and if there are two such vertices, we can pick either).
Now, let’s divide all vertices into groups based on which child subtree of the centroid they belong to, adding the centroid itself to the smallest group. Notice that the sizes of all groups still do not exceed $$$\frac{n - 1}{2}$$$. Therefore, we can pair up the vertices in such a way that each pair contains vertices from different groups. This can be done greedily using a heap in $$$O(n \log n)$$$, or by running DFS from the centroid and coloring vertices modulo $$$\frac{n - 1}{2}$$$ (clearly, with this method, no group will have two vertices of the same color), which has complexity $$$O(n)$$$.
Thus, we are left to determine which edge we should remove so that the total sum of the minimal subtree sizes across all edges in the original tree decreases as little as possible. Note that, since initially the tree has an odd number of vertices, its centroid is uniquely defined and will not change no matter which edge we remove. At the same time, since all paths pass through the centroid, the total sum of their lengths can be rewritten as the sum of distances to the centroid.
Now, let’s make two observations:

1. It is more beneficial to remove a leaf than any other type of vertex.
2. Among all leaves, it is best to remove the one closest to the centroid.

The second observation follows directly from the first and the earlier remark, so we only need to justify the first one. But this is fairly obvious: when we remove an edge, besides subtracting the depth of its nearest vertex, we also decrease the depths of all vertices in its subtree by one. Therefore, it will always be better to remove deeper edges rather than shallower ones.
As a result, after finding the centroid in $$$O(n)$$$, we get an overall complexity of $$$O(n \log n)$$$ (if we use a heap) or $$$O(n)$$$.

#include <cstdio>
#include <vector>

#define S 200005

using namespace std;
typedef long long l;

l coloring[S], centroid, best, best_dist, n, color;
vector<vector<l>> g;

l search_centroid(l u, l from) {
  l sum = 0;
  bool f = true;
  for (l v : g[u]) if (v != from) {
    l t = search_centroid(v, u);
    if (t > n / 2) f = false;
    sum += t;
  }
  
  if (f && n - 1 - sum <= n / 2) centroid = u;
  return sum + 1;
}

void make_coloring(l u, l from, l dist) {
  coloring[u] = (color++) % (n / 2) + 1;
  if (g[u].size() == 1 && dist < best_dist) {
    best_dist = dist;
    best = u;
  }
  for (l v : g[u]) if (v != from)
    make_coloring(v, u, dist + 1);
}

void solve() {
  centroid = -1, best_dist = S, color = 0;
  scanf("%lld", &n);
  g.assign(n, vector<l>());
  for (l i = 0; i < n - 1; ++i) {
    l u, v; scanf("%lld %lld", &u, &v); --u, --v;
    g[u].push_back(v); g[v].push_back(u);
  }
  
  search_centroid(1543 % n, -1);
  make_coloring(centroid, -1, 0);
  
  l bbest = max(best, g[best][0]);
  coloring[centroid] = coloring[bbest];
  coloring[bbest] = 0;
  
  printf("%lld %lld\n", best + 1, g[best][0] + 1);
  for (l i = 0; i < n; ++i) {
    if (i) printf(" ");
    printf("%lld", coloring[i]);
  }
  printf("\n");
}

int main() {
  l tc; scanf("%lld", &tc);
  while (tc--) solve();
}

It can be shown that for any array $$$ A $$$ obtained after collapsing all $$$ n $$$ towers, we can also obtain any other array $$$ B $$$ whose elements do not exceed the elements of $$$ A $$$. A strict formal proof is provided in the spoiler below; here is a brief explanation. Suppose $$$ k $$$ blocks fell onto the $$$ i $$$-th tower over the entire process. Then, for its height in the final array to be $$$ A_i $$$, $$$ A_i $$$ blocks must have fallen after its collapse, while the remaining $$$ k - A_i $$$ blocks fell before. Thus, we can always rearrange the order in which the towers collapse so that its height becomes $$$ B_i \leq A_i $$$. In other words, we ensure that $$$ B_i $$$ blocks fall onto the $$$ i $$$-th tower after its collapse, and $$$ k - B_i $$$ fall before.

From this claim about the possibility of obtaining a smaller array, two facts follow:

1. For any answer $$$\text{MEX} = x$$$, we can also obtain the answer $$$ x - 1 $$$. This means we can apply binary search on the answer.

2. For any answer $$$\text{MEX} = x$$$, we can achieve it in the form $$$[0, 0, 0, 0, \ldots, 1, 2, 3, \ldots, x - 1]$$$. Thus, at each iteration of the binary search, we need to check the possibility of obtaining such an array. To do this, we traverse the towers from left to right, tracking the number of cubes that fall onto each tower at some point and collapsing each tower after the required number of cubes have fallen onto it. The most efficient way to track the number of cubes is using the scanline method.

In total, there are $$$\text{O}(\log n)$$$ iterations in the binary search over the answer and $$$\text{O}(n)$$$ operations per iteration.

The final complexity is $$$\text{O}(n \log n)$$$.

Let the array $$$a$$$ of length $$$n$$$ be some input data for the problem.

Let $$$r$$$ and $$$r'$$$ be arrays of length $$$n$$$ such that $$$\forall i : 0 \leq r'_i \leq r_i$$$.

Assertion 1: Suppose there exists a permutation $$$p$$$ such that the tower with index $$$i$$$ collapses $$$p_i$$$-th in order, resulting in the array $$$r$$$. Then, there exists a permutation $$$p'$$$ such that the tower with index $$$i$$$ collapses $$$p'_i$$$-th in order, resulting in the array $$$r'$$$.

$$$\square$$$

Let $$$s_i$$$ be the total number of towers that ever fell onto position $$$i$$$ when collapsing the towers in the order $$$p$$$. Note that out of these, $$$r_i$$$ towers were collapsed later than the $$$i$$$-th, and the rest were collapsed earlier. The height of the $$$i$$$-th tower at the moment of its collapse is $$$a_i + (s_i - r_i)$$$.

Inductive hypothesis: There exists a permutation $$$p^{(k)}$$$ of numbers from $$$1$$$ to $$$k \leq n$$$ such that if the $$$i$$$-th tower is collapsed $$$p^{(k)}_i$$$-th in order, then:

1. The resulting height at the $$$i$$$-th position will be $$$r'_i$$$.

2. The number (denoted as $$$s^{(k)}_i$$$) of towers that fell onto position $$$i$$$ when collapsing the towers in the order $$$p^{(k)}$$$ is greater than or equal to $$$s_i$$$.

Base case: The permutation $$$p^{(1)} = [1]$$$. After collapsing, the tower's height becomes $$$0$$$, so $$$r'_1 = r_1 = 0$$$ in any resulting array. $$$s^{(1)}_1 = s_1 = 0$$$.

Inductive step: Suppose the permutation $$$p^{(k - 1)}$$$ exists. We prove the existence of $$$p^{(k)}$$$.

$$$\forall i \leq k - 1$$$, the height of the $$$i$$$-th tower at the moment of collapse under the order $$$p^{(k - 1)}$$$ is no less than under the order $$$p$$$:

From this, it follows that when collapsing in the order $$$p^{(k - 1)}$$$, at least $$$s_k$$$ towers will fall onto position $$$k$$$ (let their count be $$$x \geq s_k \geq r'_k$$$). This is because the heights at the moment of collapse for all towers $$$i \lt k$$$ have either remained the same or increased.

If $$$x \gt r'_k$$$, let tower $$$j$$$ be the $$$(x - r'_k)$$$-th tower among those that fell onto position $$$k$$$. Then, collapse tower $$$k$$$ immediately after tower $$$j$$$. If $$$x = r'_k$$$, collapse tower $$$k$$$ first. In both cases, after collapsing $$$k$$$, $$$r'_k$$$ towers will fall onto it, and its height will become $$$r'_k$$$.

Formally, for $$$x \gt r'_k$$$, the permutation $$$p^{(k)}$$$ is constructed as follows:

1. $$$\forall i \lt k : p^{(k - 1)}_i \leq p^{(k - 1)}_j \Rightarrow p^{(k)}_i = p^{(k - 1)}_i$$$

2. $$$p^{(k)}_k = p^{(k - 1)}_j + 1$$$

3. $$$\forall i \lt k : p^{(k - 1)}_i \gt p^{(k - 1)}_j \Rightarrow p^{(k)}_i = p^{(k - 1)}_i + 1$$$

For $$$x = r'_k$$$:

1. $$$p^{(k)}_k = 1$$$

2. $$$\forall i \lt k : p^{(k)}_i = p^{(k - 1)}_i + 1$$$

The array $$$s^{(k)}$$$ is constructed as $$$\forall i \lt k : s^{(k)}_i = s^{(k - 1)}_i$$$ and $$$s^{(k)}_k = x$$$.

The induction is proven. Thus, we set $$$p' = p^{(n)}$$$, and the assertion is proven.

$$$\blacksquare$$$

Corollary 1: If we can obtain $$$\text{MEX}(r) \gt 0$$$ as the answer to the problem for the resulting array $$$r$$$, then we can also obtain $$$\text{MEX}(r) - 1$$$ as the answer to the problem.

$$$\square$$$

Set $$$r'_i = \max(0, r_i - 1)$$$. Then, by Assertion 1, $$$r'$$$ can be obtained as the resulting array. $$$\text{MEX}(r') = \text{MEX}(r) - 1$$$.

$$$\blacksquare$$$

Corollary 2: If we can obtain $$$\text{MEX}(r)$$$ as the answer to the problem for the resulting array $$$r$$$, then we can obtain $$$\text{MEX}(r') = \text{MEX}(r)$$$ for the resulting array $$$r'$$$, where $$$r'_i = \max(0, (\text{MEX}(r) - 1) - (n - i))$$$.

$$$\square$$$

By Assertion 1, $$$r'$$$ can be obtained as the resulting array.

$$$\blacksquare$$$

We can perform binary search on the answer (from Corollary 1), and at each iteration, when checking the answer $$$x$$$, verify whether we can obtain the resulting array $$$r$$$ of the form $$$r_i = \max(0, (x - 1) - (n - i))$$$ (from Corollary 2).

#include <cstdio>
#include <algorithm>
#include <cstring>

#define S 100005

typedef long long l;
 
l a[S], d[S], n;

bool check(l ans) {
    memset(d, 0, sizeof(l) * n);
    l acc = 0;
    
    for (l i = 0; i < n; ++i) {
        acc -= d[i];
        
        l need = std::max(0LL, i - (n - ans));
        if (acc < need) return false;
        
        l end = i + a[i] + (acc++) - need + 1;
        if (end < n) ++d[end];
    }
    
    return true;
}

void solve() {
    scanf("%lld", &n);
    for (l i = 0; i < n; ++i) scanf("%lld", &a[i]);
    
    l le = 1, ri = n + 1, mid;
    while (ri - le > 1) {
        mid = (le + ri) / 2;
        if (check(mid)) le = mid;
        else ri = mid;
    }
    
    printf("%lld\n", le);
}

int main() {
    l tc; scanf("%lld", &tc);
    while (tc--) solve();
}