Considering an array a of n (n≥2) positive integers, the following inequality holds for 2≤i≤n: gcd($$$a_1$$$,$$$a_2$$$,⋯,$$$a_i$$$)≤gcd($$$a_1$$$,$$$a_2$$$)≤2

Therefore, when the prefix [$a_1$,$$$a_2$$$] of a is good, we can show that all the prefixes of a whose length is no less than 2 are good, then a is beautiful. It is obvious that [$$$a_1$$$,$$$a_2$$$] is good when a is beautiful. So we get the conclusion that a is beautiful if and only if the prefix [$$$a_1$$$,$a_2$] is good.

We can check if there exist $$$a_i$$$,$$$a_j$$$ (i≠j) such that gcd($$$a_i$$$,$$$a_j$$$)≤2. If so, we can move $$$a_i$$$,$$$a_j$$$ to the front of a to make it beautiful, then the answer is Yes. If not, the answer is No.

Time complexity: O($$$n^2$$$log$$$10^6$$$).

import math

def solve():
    n = int(input())
    a = list(map(int, input().split()))

    for i in range(n):
        for j in range(i + 1, n):
            if math.gcd(a[i], a[j]) <= 2:
                print("Yes")
                return
    print("No")

def main():
    t = int(input())
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

If s is palindromic initially, we can operate on the interval [1,n], the answer is Yes.

Let's consider the other case. In a palindrome s, for each i in [1,⌊n/2⌋], $$$s_i$$$=$$$s_{n−i}$$$+1 must hold. For those i, we may check whether $$$s_i$$$=$$$s_{n−i}$$$+1 is true in the initial string. For all the illegal positions i, the operation must contain either i or n+1−i , but not both. For the legal positions, the operation must contain neither of i nor n+1−i, or both of them.

If the illegal positions is continuous (which means that they are l,l+1,…,r−1,r for some l and r), we may operate on the interval [l,r] (or [n+1−r,n+1−l]), making the string palindromic. The answer is Yes.

Otherwise, there must be some legal positions that lie between the illegal ones. Suppose the illegal positions range between [l,r] (but not continuous), and the operation is [$o_1$,$$$o_2$$$]. Without loss of generality, let the operation lies in the left part of the string. Then $$$o_1$$$≤l,r≤$$$o_2$$$<n+1−r must hold to correct all the illegal positions. This interval covers all the legal positions that lie between the illegal ones but does not cover their symmetrical positions. Thus, such kind of operation will produce new illegal positions. In other words, there are no valid operations in this situation. The answer is No.

Time complexity: O(n).

def solve():
    n = int(input())
    s = input()

    l = 0
    r = n
    while l < r and s[l] == s[r - 1]:
        l += 1
        r -= 1
    if l >= r:
        print("Yes")
        return
    while l < r and s[l] != s[r - 1]:
        l += 1
        r -= 1
    while l < r and s[l] == s[r - 1]:
        l += 1
        r -= 1
    if l >= r:
        print("Yes")
    else:
        print("No")

def main():
    t = int(input())
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

Put the negative elements into an array, sort them, and find the sum of m largest modulus.

def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    
    ans = 0
    for i in range(m):
        ans += max(0, -a[i])
    
    print(ans)

if __name__ == "__main__":
    main()

Let's iterate over the length of the first segment of the split. Having fixed it, we actually fixed the sum that needs to be collected on all other segments. Since each element must belong to exactly one segment, we can build other segments greedily. If we have found a solution, we will remember the length of the longest segment in it and try to update the answer. We have n possible lengths of the first segment, for each of which we greedily built the answer for n.

Thus, the asymptotics of the solution will be O(n^2).

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    s = [0] * (n + 1)
    
    for i in range(n):
        s[i + 1] = s[i] + a[i]
    
    ans = n
    for i in range(1, n + 1):
        res = i
        k = i
        for j in range(i + 1, n + 1):
            if s[j] == s[k] + s[i]:
                res = max(res, j - k)
                k = j
        if k == n:
            ans = min(ans, res)
    
    print(ans)

def main():
    t = int(input())
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()