First, there exists an optimal answer, in which there are no more than two elements of each color.

Proof: let there exist an optimal answer, in which there are more elements of some color than 2. Then, take the median among the elements of this color and paint in another new color in which no other elements are painted. Then the maximum and minimum among the original color will not change, and in the new color the answer is 0, so the answer remains the same.

Also, if there are two colors with one element each, they can be combined into one, and the answer will not decrease.

It turns out that the numbers are paired (probably except for one; we'll assume it's paired with itself). Sort the array, and then the answer is

Unable to parse markup [type=CF_MATHJAX]

Unable to parse markup [type=CF_MATHJAX]

Unable to parse markup [type=CF_MATHJAX]

Total complexity: O(nlogn) for sorting.

def solve():
    n = int(input())
    a = [int(x) for x in input().split()]
    a.sort()
    ans = 0
    for i in range(n // 2):
        ans += a[-i-1] - a[i]
    print(ans)
    
    
t = int(input())
for _ in range(t):
    solve()

We can delete all zeros from the array, and it won't affect on answer.

Maximum sum is ∑ni=1|ai|. Minimum number of operations we should do — number of continuous subsequences with negative values of elements.

Total complexity: O(n)

T = int(input())
for _ in range(T):
    n = int(input())
    a = list(map(int, input().split()))
    
    sum = 0
    cnt = 0
    open = False
    for x in a:
        sum += abs(x)
        if x < 0 and not open:
            open = True
            cnt += 1
        if x > 0:
            open = False
 
    print(sum, cnt)

One possible solution is to represent a range of equal element as a single element with that value. Construct this array b and loop through it and check how many element bi satisfy the conditions i=0 or bi−1bi+1. If exactly one index satisfies these conditions, print "YES" and othewise "NO".

Complexity: O(n)

#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    int n;
    std::cin >> n;
    
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    
    n = std::unique(a.begin(), a.end()) - a.begin();
    
    int cnt = 0;
    
    for (int i = 0; i < n; i++) {
        if ((!i || a[i] < a[i - 1]) && (i == n - 1 || a[i] < a[i + 1])) {
            cnt++;
        }
    }
    
    if (cnt == 1) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

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

Let's note that for each second of color c in the traffic light, we need to find the rightmost green time, and then find the largest distance between color c and the nearest green. Also, let's not forget that traffic light states are cyclical.

To get rid of cyclicity, you can write the string s twice and for each cell of color c from the first half, find the nearest green color (thus we solved the problem with cyclicity). And now we can just follow this line from right to left and maintain the index of the last occurrence of green. If we encounter color c, then we try to update our answer ans=max(ans,last−i), where ans is our answer, last is the nearest time that green was on color, i — current time.

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

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

  int t;
  cin >> t;

  while (t--) {
    int n;
    char c;
    string s;
    cin >> n >> c >> s;

    int ans = 0, last = 0;
    for (int i = 2 * n - 1; i >= 0; i--) {
      int j = i % n;
      if (s[j] == 'g')
        last = i;
      if (s[j] == c)
        ans = max(ans, last - i);
    }

    cout << ans << '\n';
  }
}

Let's rewrite the inequality from ai+aj>bi+bj to (ai−bi)+(aj−bj)>0. This looks much simpler. Let's build the array c where ci=ai−bi and sort this array. Now our problem is to find the number of pairs i<j such that ci+cj>0.

Let's iterate over all elements of c from left to right. For simplicity, we consider only "greater" summands. Because our sum (ci+cj) must be greater than 0, then at least one of these summands will be positive. So, if ci≤0, just skip it. Now ci>0 and we need to calculate the number of such j that ci+cj>0 and j<i. It means that each cj≥−ci+1 (for some j<i) will be okay. Such leftmost position j can be found with std::lower_bound or binary search. Then add the value i−j to the answer and consider the next element.

Time complexity: O(nlogn).

n = int(input())

A = list(map(int, input().split()))
B = list(map(int, input().split()))
D = [0] * n

for i in range(n):
    D[i] = A[i] - B[i]

D.sort()

# find pairs which gives Di + Dj > 0

total = 0
beg = 0
end = n - 1

while (end >= beg):
    while (beg < end and D[beg] + D[end] <= 0):
        beg += 1
    total += max(end - beg, 0)
    end -= 1

print(total)