Find the length n of the string, and then print first n-2 chars and then i.

Let n be the length of the string.
Answer is either 1 or n

If there exists adjacent 2 equal chars, we can reduce the string to length 1.
The idea is we remove these 2 equal chars, and then replace them with one nearby char, thereby ensuring that we still have 2 adjacent equal chars.

Greedy.
For each i, try to find a minimum value of ai which we can get and it is still sorted.

If K is the minimum possible value of a_{i-1} we can get such that the array is still sorted.

If we do not do any operation the value remains ai. This is possible only if K <= ai

If we do an operation then bj — ai >= K, this imples aj+K <= bj.
So chose the minimum bj >= aj+K, and do an operation using it.

Score of an array is sum of prefix sum of the array.
For an index idx = i*m+j, S_{idx} = sum of first i-1 arrays + sum of first j elements of ith array.

Try to find both of these values separately.

Contribution due to part 2 is sum of score of all arrays.

Let C = [sum(a1),sum(a2),sum(a3),...,sum(an)]
Let S = maximum score we can get after rearranging C.
Then contribution due to part 1 is m*S

max(x-y,y-x) is equal to abs(x-y)
First try to find trivial -1 cases.

Look at the complete string first. The score is abs(n-m).
If this is more than K, then maximum balance among all substring is more than K.

If n<k and m<k, then balance can never be equal K.

Otherwise the following string works for N=10, M = 11, and K = 3
111 000 111 000 111 000 11 0

If an array has a majority element, then there must exist a subarray with length 2 or 3 with that element being majority.

The problem reduces to checking length 2 and 3 paths.

Length 2 paths are just edges.

For length 3, you can fix a middle element and check if 2 adjacent elements contain same value.

There arent many cases when lcm is semi prime.

If p and q are different prime nos, then their lcm p*q is semi prime.

Otherwise, one of the element must be semi prime, and other one must be its factor.

f(t) can also be written as 1 + no of adjacent different chars.

Lets look contribution due to si and sj being adjacent.
If si==sj, they add 0 to score.
If si!=sj, then they add 1 to score.
No of subsequences that contain si and sj adjacent are pow(2,i-1)*pow(2,n-j), basically,
- For char before i, we have 2 choices we can take them or ignore them.
- For char after j, we have 2 choices we can take them or ignore them.
- We must take i and j
- We must not take chars between i and j

Now, the hard part, how to do it with changing chars?
Use Segment tree.

For each node representing s[i...j], we can maintain -
- Sum of pow(2,i-1) when si = 0
- Sum of pow(2,i-1) when si = 1
- Sum of pow(2,n-j) when sj = 0
- Sum of pow(2,n-j) when sj = 1
- Contribution due to pairs inside this segment