If sum is even, answer is $$$0$$$. Otherwise we need to change parity of atleast one element of $$$a$$$.

It it optimal to change parity of atmost one element.

Answer can be atmost $$$20$$$, as we need to divide any integer $$$x$$$ ($$$1 \leq x \leq 10^6$$$) atmost $$$20$$$ times to change its parity.

We are assuming initial sum is odd. Suppose $$$f(x)(1 \leq x \leq 10^6)$$$ gives the minimum number of operations needed to change parity of $$$x$$$.

Iterate from $$$i=1$$$ to $$$n$$$ and calculate $$$f(a_i)$$$ for each $$$i$$$.

Answer is minimum among all the calculated values.

Time complexity is $$$O(n \cdot log(A_{max}))$$$.

#include <bits/stdc++.h>     
using namespace std;
#define ll long long
void solve(){
    ll n; cin>>n;
    ll sum=0,ans=21;
    vector<ll> a(n);
    for(auto &it:a){
        cin>>it;
        sum+=it;
    }
    if(sum&1){
        for(auto &it:a){
            ll cur=it,now=0;
            while(!((cur+it)&1)){
                now++;
                cur/=2;
            }
            ans=min(ans,now);
        }
    }
    else{
        ans=0;
    }
    cout<<ans<<"\n";
}
int main()                                                                                
{  
    ios_base::sync_with_stdio(false);                         
    cin.tie(NULL);  
    ll t; cin>>t;
    while(t--){
        solve();
    }
} 

Suppose we have a prime number $$$p$$$. Suppose there are two perfect powers of $$$p$$$ — $$$l$$$ and $$$r$$$. Now it is easy to see $$$\max(l,r)$$$ is divisible by $$$\min(l,r)$$$.

So now we need to choose some prime number $$$p$$$. Let us start with the smallest prime number $$$p=2$$$.

Here is one interesting fact. There always exists a power of $$$2$$$ in the range $$$[x,2x]$$$ for any positive integer $$$x$$$.

Suppose $$$f(x)$$$ gives the smallest power of $$$2$$$ which is greater than $$$x$$$.

Iterate from $$$i=1$$$ to $$$n$$$ and change $$$a_i$$$ to $$$f(a_i)$$$ by adding $$$f(a_i)-a_i$$$ to $$$i$$$-th element.

Time complexity is $$$O(n \cdot log(A_{max}))$$$.

#include <bits/stdc++.h>     
using namespace std;
#define ll long long
ll f(ll x){
    ll cur=1;
    while(cur<=x){
        cur*=2;
    }
    return cur;
}
void solve(){
    ll n; cin>>n;
    cout<<n<<"\n";
    for(ll i=1;i<=n;i++){
        ll x; cin>>x;
        cout<<i<<" "<<f(x)-x<<"\n";
    }
}
int main()                                                                                
{  
    ios_base::sync_with_stdio(false);                         
    cin.tie(NULL);  
    ll t; cin>>t;
    while(t--){
        solve();
    }
} 

Let us first find $$$f(s[1,n])$$$.

$$$f(s[1,n])=2^{len-1}$$$ where $$$len$$$ is the length of longest suffix of $$$s$$$ in which all characters are same.

How to prove the result in hint $$$2$$$?

First of all it is easy to see if all characters of $$$s$$$ are same, $$$f(s[1,n])=2^{n-1}$$$ as median is always $$$s_i$$$.

Now we assume that $$$s$$$ contains distinct characters.

Suppose $$$t$$$ is one good extension of $$$s$$$. Assume we are index $$$i$$$. If there exists an index $$$j(j>i)$$$ such that $$$s_i \neq s_j$$$, we should have $$$t_{2i} \neq s_i$$$.

Why? Assume $$$k$$$ is the smallest index greater than $$$i$$$ such that $$$s_i \neq s_k$$$. Now if we have $$$t_{2i} = s_i$$$, $$$s_k$$$ can never be median of subarray $$$t[1,2k-1]$$$. So if longest suffix of $$$s$$$ having same characters of starts at index $$$i$$$, $$$t_{2j} \neq s_j$$$ for all $$$j(1 \leq j < i)$$$ and $$$t_{2j}$$$ can be anything(either $$$0$$$ or $$$1$$$) for all $$$j(i \leq j < n)$$$.

Now we know how to solve for whole string $$$s$$$.

We can similarly solve for all prefixes.

To find $$$f(s[1,i])$$$, we need to find the longest suffix of $$$s[1,i]$$$ containing same character.

We can easily calculate this all prefixes while moving from $$$i=1$$$ to $$$n$$$.

Time complexity is $$$O(n)$$$.

#include <bits/stdc++.h>     
using namespace std;
#define ll long long
const ll MOD=998244353;
void solve(){
    ll n; cin>>n;
    string s; cin>>s; s=" "+s;
    ll ans=0,cur=1;
    for(ll i=1;i<=n;i++){
        if(s[i]==s[i-1]){
            cur=(2*cur)%MOD;
        }
        else{
            cur=1;
        }
        ans=(ans+cur)%MOD;
    }
    cout<<ans<<"\n";
}
int main()                                                                                
{  
    ios_base::sync_with_stdio(false);                         
    cin.tie(NULL);  
    ll t; cin>>t;
    while(t--){
        solve();
    }
} 

Intended solution uses $$$2 \cdot (n-2)$$$. You are allowed to guess two indices. Doesn't this hint towards something?

If we can eliminate $$$n-2$$$ elements that cannot be $$$0$$$ for sure, we are done.

Suppose we have three distinct indices $$$i$$$, $$$j$$$ and $$$k$$$. Is it possible to remove one index(say $$$x$$$) out of these three indices such that $$$p_x \neq 0$$$ for sure. You are allowed to query two times.

So suppose we have three distinct indices $$$i$$$, $$$j$$$ and $$$k$$$.

Let us assume $$$l=query(i,k)$$$ and $$$r=query(j,k)$$$

Now we have only three possibilities.

• $$$l=r$$$ In this case, $$$p_k$$$ cannot be $$$0$$$. Why? $$$p_i$$$ and $$$p_j$$$ are distinct, and we have $$$\gcd(0,x) \neq \gcd(0,y)$$$ if $$$x \neq y$$$

• $$$l > r$$$ In this case, $$$p_j$$$ cannot be $$$0$$$. Why? Note $$$\gcd(0,p_k)=p_k$$$ and $$$\gcd(m,p_k)$$$ can be atmost $$$p_k$$$ for any non negative integer. If $$$l > r$$$, this means $$$r$$$ cannot be $$$p_k$$$. Thus $$$p_r \neq 0$$$ for sure

• $$$l < r$$$ In this case, $$$p_i$$$ cannot be $$$0$$$. Why? Refer to the above argument.

This we can eliminate one index on using $$$2$$$ queries. We will perform this operation $$$n-2$$$ times. Refer to attached code for details.

Time complexity is $$$O(n)$$$.

#include <bits/stdc++.h>     
using namespace std;
#define ll long long
void solve(){
    ll n; cin>>n;
    ll l=1,r=2;
    for(ll i=3;i<=n;i++){
        ll ql,qr;
        cout<<"? "<<l<<" "<<i<<endl;
        cin>>ql;
        cout<<"? "<<r<<" "<<i<<endl;
        cin>>qr;
        if(ql>qr){
            r=i;
        }
        else if(ql<qr){
            l=i;
        }
    }
    cout<<"! "<<l<<" "<<r<<endl;
    ll check; cin>>check;
    assert(check==1); 
}
int main()                                                                                
{  
    ios_base::sync_with_stdio(false);                         
    cin.tie(NULL);  
    ll t; cin>>t;
    while(t--){
        solve();
    }
} 

There does not exist any good tree of size $$$n$$$ if $$$n$$$ is odd.

How to prove it? Suppose $$$f(v)$$$ gives the product of weight of edges incident to node $$$v$$$ in a good tree. We know that $$$f(i)=-1$$$ as if tree is good. Now $$$\prod_{i=1}^{n} f(i) = -1$$$ if $$$n$$$ is odd.

There is another way to find $$$\prod_{i=1}^{n} f(i)$$$. Look at contribution of each edge. Each edge contribitues $$$1$$$ to $$$\prod_{i=1}^{n} f(i)$$$, no matter what the weight of this edge is, as it gets multiplied twice. Thus we get $$$\prod_{i=1}^{n} f(i) = 1$$$. We got contradiction. Thus no good tree of size $$$n$$$ exists.

Now assume $$$n$$$ is even.

Here is an interesting claim.

For any unweighted tree,there exists exactly one assignment of weight of edges which makes it good.

Thus there are $$$n^{n-2}$$$ distinct edge-weighted trees.

How to prove the claim in hint $$$2$$$?

Arbitrarily root the tree at node $$$1$$$.

Now start from leaves and move towards root and assign the weight of edges in the path.

First of all the edge incident to any leaf node will have $$$-1$$$ as the weight. While moving towards root, it can be observed that weight of edge between $$$u$$$ and parent of $$$u$$$ depends on the product of weight of edges between $$$u$$$ and its children.

As we are moving from leaves towards root, weight of edges between $$$u$$$ and its children are already fixed. Weight of edge between $$$u$$$ and parent $$$u$$$ is $$$-1 \cdot \prod_{x \in C(u)}{pw(x)}$$$, where $$$pw(x)$$$ gives the weight of edge between $$$x$$$ and its parent, and $$$C(u)$$$ denotes the set of children of $$$u$$$.

Time for one more interesting claim. The weight of edge $$$e$$$ is $$$(-1)^{l}$$$ if there are $$$l$$$ nodes on one side and $$$n-l$$$ nodes on other side of $$$e$$$, irrespective of the structure of tree.

We can prove this claim by induction, similar to what we did in hint $$$3$$$.

To find answer we will look at contribution of each edge.

Here's detailed explanation on how to dot it.

In total, we have $$$n^{n-2} \cdot (n-1)$$$ edges.

Suppose for some edge(say $$$e$$$), we have $$$l$$$ nodes(including node $$$1$$$) on left side and $$$r$$$ nodes(including node $$$n$$$) on right side.

Among $$$n^{n-2} \cdot (n-1)$$$ edges, how many possibilities do we have for $$$e$$$?

It is $$${{n-2} \choose {l-1}} \cdot l \cdot r \cdot l^{l-2} \cdot r^{r-2}$$$. Why? First we select $$$l-1$$$ nodes(as node $$$1$$$ is fixed to be on left side) to be on left side, we get $$${{n-2} \choose {l-1}}$$$ for this.

Now we have $$$l$$$ nodes on left side and $$$r$$$ nodes on right side. Edge $$$e$$$ will connect one among $$$l$$$ nodes on left and one among $$$r$$$ nodes on right. So edge $$$e$$$ will exist between $$$l \cdot r$$$ pairs. We know that number of distinct trees having $$$x$$$ nodes is $$$x^{x-2}$$$.

Now on selecting one node from left and one from right, we have fixed the root of subtree on left side, and have also fixed the root of subtree on right side. So, number of distinct subtrees on left side is $$$l^{l-2}$$$, and number of distinct subtrees on right side is $$$r^{r-2}$$$.

Thus, on mutliplying all(since they are independent), we get $$${n \choose l} \cdot l \cdot r \cdot l^{l-2} \cdot r^{r-2}$$$ possibilities for $$$e$$$.

Now this edge lies on the path from $$$1$$$ to $$$n$$$ as both lie on opposite sides of this node.

So this edge contributes $$$(-1)^l \cdot {{n-2} \choose {l-1}} \cdot l \cdot r \cdot l^{l-2} \cdot r^{r-2}$$$ to answer.

Hence $$$d(1,n)=\sum_{l=1}^{n-1} (-1)^l \cdot {{n-2} \choose {l-1}} \cdot l \cdot r \cdot l^{l-2} \cdot r^{r-2}$$$ where $$$l+r=n$$$. Note that we assumed that we are always going from left subtree to right subtree while calculating contribution. As we have tried all possibilties for l, all cases get covered. We used left and right subtrees just for our own convention.

Time complexity is $$$O(n \cdot \log(n))$$$.

#include <bits/stdc++.h>     
using namespace std;
#define ll long long
const ll MOD=998244353;
const ll MAX=500500;
vector<ll> fact(MAX+2,1),inv_fact(MAX+2,1);
ll binpow(ll a,ll b,ll MOD){
    ll ans=1;
    a%=MOD;  
    while(b){
        if(b&1)
            ans=(ans*a)%MOD;
        b/=2;
        a=(a*a)%MOD;
    }
    return ans;
}
ll inverse(ll a,ll MOD){
    return binpow(a,MOD-2,MOD);
} 
void precompute(ll MOD){
    for(ll i=2;i<MAX;i++){
        fact[i]=(fact[i-1]*i)%MOD;
    }
    inv_fact[MAX-1]=inverse(fact[MAX-1],MOD);
    for(ll i=MAX-2;i>=0;i--){
        inv_fact[i]=(inv_fact[i+1]*(i+1))%MOD;
    }
}
ll nCr(ll a,ll b,ll MOD){
    if((a<0)||(a<b)||(b<0))
        return 0;   
    ll denom=(inv_fact[b]*inv_fact[a-b])%MOD;
    return (denom*fact[a])%MOD;  
}
void solve(){         
    ll n,ans=0; cin>>n;
    if(n&1){  
        cout<<0;    
        return;
    }
    ll sgn=1;  
    for(ll i=1;i<n;i++){ 
        sgn*=-1; 
        ll r=n-i,l=i;
        ll fix_l=nCr(n-2,l-1,MOD); //fixing l nodes on left side  
        ll fix_root=(l*r)%MOD; //fixing roots of subtrees on both sides 
        ll trees=(binpow(l,l-2,MOD)*binpow(r,r-2,MOD))%MOD; //counting no of subtrees
        ll no_of_e=(((fix_l*fix_root)%MOD)*trees)%MOD; //no of possibilities for e
        ans=(ans+sgn*no_of_e)%MOD;
    }     
    ans=(ans+MOD)%MOD;          
    cout<<ans; 
    return;            
} 
int main()                                                                                
{  
    ios_base::sync_with_stdio(false);                         
    cin.tie(NULL);  
    precompute(MOD);
    ll t=1; 
    //cin>>t;
    while(t--){
        solve();
    }
} 

We should have $$$|a_{i_j}-a_{i_{j+1}}| \leq k$$$. This seems a bit hard, as we can have $$$a_{i_{j+1}}$$$ greater than, smaller than or equal to $$$a_{i_j}$$$.

Why not solve the easier version first?

A pair $$$(l,r)$$$ is good if there exists a sequence of indices $$$i_1, i_2, \dots, i_m$$$ such that

• $$$i_1=l$$$ and $$$i_m=r$$$;
• $$$i_j < i_{j+1}$$$ for all $$$1 \leq j < m$$$; and
• $$$0 < a_{i_j}-a_{i_{j+1}} \leq k$$$ for all $$$1 \leq j < m$$$.

Suppose $$$F(a,k)$$$ number of pairs $$$(l,r)$$$ ($$$1 \leq l < r \leq n$$$) that are good.

Find $$$F(a,k)$$$.

To solve the problem in hint $$$1$$$, let us define $$$dp_i$$$ as the number of pairs $$$j(i<j)$$$ such that $$$(i,j)$$$ is good.

Let us move from $$$i=n$$$ to $$$1$$$. To find $$$dp_i$$$, let us first find the smallest index $$$j$$$ such that $$$a_j$$$ lies in range $$$[a_i+1,a_i+k]$$$.

We can observe that $$$dp_i=dp_j+f(i,a_i+1,a_j)$$$, where $$$f(i,l,r)$$$ gives us the number of indices $$$x$$$ among last $$$i$$$ elements of $$$a$$$ such that $$$a_x$$$ lies in the range $$$[l,r]$$$. We can use fenwik tree or ordered set to find $$$f(i,l,r)$$$.

Now let us get back to original problem.

First let us count number of pairs $$$(i,j)(1 \leq i \leq j)$$$ such that $$$a_i=a_j$$$. Assume $$$cnt$$$ is number of such pairs.

Time for another cool claim!

For our original problem, answer is $$$cnt+F(a,k)+F(rev(a),k)$$$, where $$$rev(a)$$$ denotes the array $$$a$$$ when it is reversed.

How to prove the claim in hint $$$3$$$?

Suppose we have a good pair $$$(l,r)$$$ such that $$$a_l \neq a_r$$$. Now using exchange arguments we can claim that there always exists a sequence(say $$$s$$$) starting at index $$$l$$$ and ending at index $$$r$$$

• such that difference between adjacent elements of $$$a$$$ is atmost $$$k$$$
• strictly increasing if $$$a_l < a_r$$$
• strictly decreasing if $$$a_l > a_r$$$

Thus $$$(l,r)$$$ will be counted in $$$F(a,k)$$$ if $$$a_l < a_r$$$ and $$$(l,r)$$$ will be counted in $$$F(rev(a),k)$$$ if $$$a_l > a_r$$$.

Time complexity is $$$O(n \cdot \log(n))$$$.

#include <bits/stdc++.h>     
using namespace std;
#define ll long long
const ll MAX=1000100;
class ST{
public:
    vector<ll> segs;
    ll size=0;                       
    ll ID=MAX;
 
    ST(ll sz) {
        segs.assign(2*sz,ID);
        size=sz;  
    }   
   
    ll comb(ll a,ll b) {
        return min(a,b);  
    }
 
    void upd(ll idx, ll val) {
        segs[idx+=size]=val;
        for(idx/=2;idx;idx/=2){
            segs[idx]=comb(segs[2*idx],segs[2*idx+1]);
        }
    }
 
    ll query(ll l,ll r) {
        ll lans=ID,rans=ID;
        for(l+=size,r+=size+1;l<r;l/=2,r/=2) {
            if(l&1) {
                lans=comb(lans,segs[l++]);
            }
            if(r&1){
                rans=comb(segs[--r],rans);
            }
        }
        return comb(lans,rans);
    }
};
struct FenwickTree{
    vector<ll> bit; 
    ll n;
    FenwickTree(ll n){
        this->n = n;
        bit.assign(n, 0);
    }
    FenwickTree(vector<ll> a):FenwickTree(a.size()){
        ll x=a.size();
        for(size_t i=0;i<x;i++)
            add(i,a[i]);
    }
    ll sum(ll r) {
        ll ret=0;
        for(;r>=0;r=(r&(r+1))-1)
            ret+=bit[r];
        return ret;
    }
    ll sum(ll l,ll r) {
        if(l>r)
            return 0;
        return sum(r)-sum(l-1);
    }
    void add(ll idx,ll delta) {
        for(;idx<n;idx=idx|(idx+1))
            bit[idx]+=delta;
    }
};
FenwickTree freq(MAX);  
ST segtree(MAX);
vector<ll> dp(MAX,0);
ll solve(vector<ll> a,ll n,ll k){
    ll now=0;
    for(ll i=n-1;i>=0;i--){  
        ll j=segtree.query(a[i]+1,a[i]+k);
        if(j<n){
            dp[i]=dp[j]+freq.sum(a[i]+1,a[j]);
        }
        else{
            dp[i]=0;
        }
        now+=dp[i];
        segtree.upd(a[i],i);
        freq.add(a[i],1);
    }  
    for(auto it:a){  
        segtree.upd(it,MAX);  
        freq.add(it,-1); 
    }
    return now;
}
void solve(){         
    ll n,k; cin>>n>>k;
    vector<ll> a(n);
    ll ans=0;
    map<ll,ll> cnt;  
    for(auto &it:a){
        cin>>it;
        cnt[it]++;
        ans+=cnt[it];
    }
    ans+=solve(a,n,k);
    reverse(a.begin(),a.end());
    ans+=solve(a,n,k);
    cout<<ans<<"\n"; 
    return;            
} 
int main()                                                                                
{  
    ios_base::sync_with_stdio(false);                         
    cin.tie(NULL);  
    ll t=1; 
    cin>>t;
    while(t--){
        solve();
    }
} 

Answer is NO only when there exists an element of $$$a$$$ which occurs more that $$$\lceil \frac{n}{2} \rceil$$$ times.

Let us say an array $$$b$$$ is beautiful if length of $$$b$$$ is odd and mode(say $$$x$$$) of $$$b$$$ occurs exactly $$$\lceil \frac{n}{2} \rceil$$$ times.

If $$$a$$$ is beautiful, there exists only one permutation.

We have rearrange such that $$$x$$$ occupies all the odd indices and keep the elements at even indices such that condition $$$2$$$ in satisfied.

To solve the original problem, we will divide the array $$$a$$$ into multiple beautiful subarrays and arrange the elements in those subarrays.

Let us continue from where we left off.

So our motivation is to break the original array into multiple beautiful subarrays and the elements in those subarrays, as mentioned before. Now for condition $$$1$$$ to be satisfied, we should not have two adjacent subarrays such that the elements at the end positions of both subarrays(after rearranging the elements) are the same.

Here is one construction using which we can achieve our goal.

Suppose $$$l$$$ denotes the leftmost point of our concerned subarray.

If $$$a_l \neq a_{l+1}$$$, we move forward, as subarray $$$a[l,l]$$$ is good.

Otherwise, we keep moving towards the right till index $$$r$$$(here, $$$r$$$ should be the smallest possible) such that the subarray $$$a[l,r]$$$ is beautiful and $$$a_l \neq a_{r+1}$$$. So it is easy to notice the following observations about the subarray $$$a[l,r]$$$

• length of this subarray is odd

• $$$a_l$$$ occurs exactly $$$\lceil \frac{r-l+1}{2} \rceil$$$ times in this subarray

Now we can rearrange the elements of this subarray $$$a[l,r]$$$.

Do note that the subarray $$$a[1,r]$$$ satisfies both the conditions stated in the statement.

So our task is to make the subarray $$$a[r+1,n]$$$ good now.

We can now update $$$l=r+1$$$ and continue searching for the corresponding $$$r$$$ and so on.

Now it might be the case that we did not get a valid $$$r$$$ for the last search.

From here, I assume we did not get valid $$$r$$$ for the last search. We could print the obtained permutation if we got it, as $$$a$$$ would satisfy both conditions.

Assume that we had started at $$$pos=l$$$ and couldn't find $$$r$$$.

Subarray $$$a[1,pos-1]$$$ is already good.

To fix this issue, we will do a similar search that we did before.

We start from the back(from index $$$n$$$) and move towards left till index $$$m$$$ such that

• $$$m < pos$$$
• $$$a[m,n]$$$ is beautiful
• $$$a_{pos}$$$ occurs exactly $$$\lceil \frac{n-m+1}{2} \rceil$$$ times in this subarray
• $$$a_{pos} \neq a_{m-1}$$$

Now we arrange elements of this subarray in the same fashion that we did before.

Are we done?

No. First, we must prove that we will always get some $$$m$$$.

Let us have function $$$f(a,l,r,x)$$$, which denotes the score of the subarray $$$a[l,r]$$$ for the element $$$x$$$. $$$f(a,l,r,x)=freq_x-(r-l+1-freq_x)$$$, where $$$freq_x$$$ denotes the frequency of element $$$x$$$ in the subarray $$$a[l,r]$$$

It is easy to note that $$$f(a,pos,n,a_{pos}) > 1$$$

(Hint $$$ — $$$ Prove that $$$f(a,pos,r,a_{pos}) \neq 0$$$ for $$$pos \leq r \leq n$$$. Why?(If it does then $$$a[pos,r-1]$$$ would be beautiful ))

Now we start from the back and move towards the right to find $$$m$$$ with $$$n$$$ as our right endpoint of the concerned subarray.

Note that $$$f(a,1,n,a_{pos}) \leq 1$$$ (Why? $$$a_{pos}$$$ would have occurred at most $$$\lceil \frac{n}{2} \rceil$$$ times in $$$a$$$)

So while moving from $$$pos$$$ to $$$1$$$ we will indeed find a $$$m$$$ such that $$$f(a,m,n,a_{pos})=1$$$, and $$$a_{m-1} \neq a_{pos}$$$ (assuming $$$a_0=-1$$$)

Are we done?

Not still :p. We can observe that condition $$$1$$$ is satisfied, but sometimes condition $$$2$$$ would not be. For example, simulate the above approach on the array $$$a=[1,1,2,3,3]$$$.

How to fix this issue? It's pretty easy to fix this issue.

You can refer to the attached code for implementation details.

#include <bits/stdc++.h>     
using namespace std;  
#define ll long long  
#define all(x) x.begin(),x.end()     
void solve(){    
    ll n; cin>>n;
    vector<ll> a(n+5),freq(n+5,0);
    for(ll i=1;i<=n;i++){
        cin>>a[i]; freq[a[i]]++;
    }
    for(ll i=1;i<=n;i++){
        ll till=(n+1)/2;
        if(freq[i]>till){
            cout<<"NO\n";
            return;
        }
    }
    cout<<"YES\n";
    vector<ll> ans;
    ll cur=1;
    while(cur<=n){
        ll val=a[cur];
        vector<ll> v1,v2;
        while(cur<=n){
            if(a[cur]==val){
                v1.push_back(cur);
            }
            else{
                v2.push_back(cur);
            }
            if(v1.size()==v2.size()){
                for(ll i=0;i<v1.size();i++){
                    ans.push_back(v1[i]); ans.push_back(v2[i]);
                }
                ans.pop_back();
                break; 
            }
            if(cur==n){
                while(1){
                    if(ans.empty()||v1.size()==v2.size()){
                        sort(all(v1)); sort(all(v2));
                        if(v1.size()!=v2.size()){
                            ans.push_back(v1[0]);
                            v1.erase(v1.begin());
                        }
                        if(!v2.empty()&&!ans.empty()){
                            if(a[ans.back()]==a[v2[0]]){
                                swap(v1,v2);
                            }
                        }
                        for(ll i=0;i<v1.size();i++){
                            ans.push_back(v2[i]); ans.push_back(v1[i]);  
                        }
                        break;
                    }
                    if(a[ans.back()]==val){
                        v1.push_back(ans.back());
                    }
                    else{
                        v2.push_back(ans.back());
                    }
                    ans.pop_back();
                }
                cur=n+1;
            }
            cur++;
        }
    }
    for(auto it:ans){
        cout<<it<<" ";
    }
    cout<<"\n";
    return;                                
}                                                
int main()                                                                                             
{                          
    ll test_cases=1;               
    cin>>test_cases;
    while(test_cases--){
        solve();
    } 
}  

It is easy to observe that the second operation needs to be performed at most once. Now, we just need to check $$$2$$$ cases, one in which the re-arrangement operation is used, and one in which it is not.

If the re-arrangement operation is to be used, then we just need to make the counts of $$$0$$$s and $$$1$$$s in $$$a$$$ equal to that of $$$b$$$. Without loss of generality assume $$$a$$$ contains $$$x$$$ more $$$0$$$s than $$$b$$$, then the cost in this case will just be $$$x + 1$$$ (extra one for re-arrangement cost).

If the re-arrangement operation is not to be used, then we just need to make each element of $$$a$$$ equal to the corresponding element of $$$b$$$.

Finally, our answer is the smaller cost of these $$$2$$$ cases.

Time complexity is $$$O(n)$$$.

#include <bits/stdc++.h>     
using namespace std;
#define ll long long
void solve(){
    ll n; cin>>n;
    ll sum=0,ans=0;
    vector<ll> a(n),b(n);
    for(auto &it:a){
        cin>>it;
        sum+=it;
    }
    for(auto &it:b){
        cin>>it;
        sum-=it;
    }
    for(ll i=0;i<n;i++){
        ans+=(a[i]^b[i]);
    }
    ans=min(ans,1+abs(sum));
    cout<<ans<<"\n";
}
int main()                                                                                
{  
    ios_base::sync_with_stdio(false);                         
    cin.tie(NULL);  
    ll t; cin>>t;
    while(t--){
        solve();
    }
}  

Take $$$a_0 = a_{n+1} = 1$$$.

Now take $$$b_i=lcm(a_{i-1},a_i)$$$ for $$$1 \leq i \leq n+1$$$. If $$$b$$$ gives us $$$a$$$ after performing the $$$\gcd$$$ operations, then the answer is YES, otherwise the answer is NO. (When answer is NO, we would get a case like $$$\gcd(b_i, b_{i + 1}) = k \cdot a_i$$$(where $$$k > 1$$$ for some $$$i$$$).

Suppose $$$c$$$ is some valid array which gives us $$$a$$$. So, $$$c_i$$$ should be divisible by $$$b_i$$$. This means $$$\gcd(c_i, c_{i+1}) \geq \gcd(b_i, b_{i + 1})$$$.

So, if $$$\gcd(b_i, b_{i + 1}) > a_i$$$ for any $$$i$$$, we should also have $$$\gcd(c_i, c_{i+1}) > a_i$$$. This implies that $$$c$$$ is not valid if $$$b$$$ is not valid.

Time complexity is $$$O(n \cdot \log(bmax))$$$.

#include <bits/stdc++.h>     
using namespace std;
#define ll long long
ll lcm(ll a,ll b){
    ll g=__gcd(a,b);
    return (a*b/g);
}
void solve(){
    ll n; cin>>n;
    vector<ll> a(n+2,1);
    for(ll i=1;i<=n;i++){
        cin>>a[i];
    }
    vector<ll> b(n+2,1);
    for(ll i=1;i<=n+1;i++){
        b[i]=lcm(a[i],a[i-1]);
    }
    for(ll i=1;i<=n;i++){
        if(__gcd(b[i],b[i+1])!=a[i]){
            cout<<"NO\n";
            return;
        }
    }
    cout<<"YES\n";
}
int main()                                                                                
{  
    ios_base::sync_with_stdio(false);                         
    cin.tie(NULL);  
    ll t; cin>>t;
    while(t--){
        solve();
    }
}  

Suppose $$$l[i]$$$ represents the leftmost point such that subarray $$$a[l[i],i]$$$ is good.

Notice that the array $$$l$$$ is non-decreasing.

So suppose $$$dp[i]$$$ denotes the length of longest good subarray which ends at index $$$i$$$.

Take $$$dp[0]=0$$$.

Now $$$dp[i]=min(dp[i-1]+1,a[i])$$$.

Suppose $$$a[i] \geq dp[i-1]+1$$$. Now we claim that $$$dp[i]=dp[i-1]+1$$$. We know $$$a[i-dp[i-1],i-1]$$$ is \t{good}. Now if we look at array $$$b=a[i-dp[i-1],i]$$$, $$$b_i \geq i $$$ for $$$ 1 \leq i \leq dp[i-1]$$$. For $$$b$$$ to be good, last element of $$$b$$$(which is $$$a[i]$$$) should be greater than or equal $$$dp[i-1]+1$$$(which is consistent with our supposition). So $$$b$$$ is good.

We can similarly cover the case when $$$a[i] < dp[i-1]+1$$$.

So our answer is $$$ \sum_{i=1}^{n} dp[i]$$$. Time complexity is $$$O(n)$$$.

#include <bits/stdc++.h>     
using namespace std;
#define ll long long
void solve(){
    ll n; cin>>n;
    vector<ll> dp(n+5,0);
    ll ans=0;
    for(ll i=1;i<=n;i++){
        ll x; cin>>x;
        dp[i]=min(dp[i-1]+1,x);
        ans+=dp[i];
    }
    cout<<ans<<"\n";
}
int main()                                                                                
{  
    ios_base::sync_with_stdio(false);                         
    cin.tie(NULL);  
    ll t; cin>>t;
    while(t--){
        solve();
    }
}  

Let us continue the idea of C1.

Suppose $$$track[i]$$$ denotes $$$\sum_{j=i}^{n} dp[j]$$$ if $$$dp[i]=a[i]$$$.

We can precalculate array $$$track$$$.

Now suppose $$$a_p$$$ is changed to $$$x$$$ and $$$adp[i]$$$ denotes the length of longest good subarray which ends at index $$$i$$$ in the updated array.

It is easy to see that $$$adp[i]=dp[i]$$$ for $$$ 1 \leq i < p$$$. Now let $$$q$$$ be the smallest index greater than $$$p$$$ such that $$$adp[q]=a[q]$$$(It might be the case that there does not exist any such $$$q$$$ which can be handled similarly). So we have $$$3$$$ ranges to deal with — $$$(1,p-1)$$$, $$$(p,q-1)$$$ and $$$(q,n)$$$.

Now $$$\sum_{i=1}^{p-1} adp[i]$$$ = $$$\sum_{i=1}^{p-1} dp[i]$$$(which can be stored as prefix sum).

Also $$$\sum_{i=q}^{n} adp[i]$$$ = $$$track[q]$$$.

Now we only left with range $$$(p,q-1)$$$. An interesting observation is $$$adp[i]=adp[i-1]+1$$$ for $$$p < i < q$$$.

This approach can be implemented neatly in many ways(one way is answer each query offline).

Time complexity is $$$O(n \cdot \log(n))$$$.

#include <bits/stdc++.h>     
using namespace std;
#define ll long long
#define f first
#define s second
int main()                                                                                
{  
    ios_base::sync_with_stdio(false);                         
    cin.tie(NULL);  
    ll n; cin>>n;
    vector<ll> track(n+5,0),sum(n+5,0);
    vector<pair<ll,pair<ll,ll>>> trav; 
    vector<ll> pref(n+5,0),dp(n+5,0);
    for(ll i=1;i<=n;i++){
        ll x; cin>>x;
        sum[i]=sum[i-1]+i; trav.push_back({x-i,{i,0}});
        dp[i]=min(dp[i-1]+1,x); pref[i]=pref[i-1]+dp[i];    
    }
    ll q; cin>>q;
    vector<ll> ans(q+5,0);  
    for(ll i=1;i<=q;i++){
        ll p,x; cin>>p>>x; x=min(dp[p-1]+1,x); 
        trav.push_back({x-p,{p,i}});
    }
    set<ll> found; found.insert(n+1);  
    sort(trav.begin(),trav.end()); 
    for(auto it:trav){
        if(it.s.s){
            ll r=*found.upper_bound(it.s.f);
            ans[it.s.s]=pref[it.s.f-1]+track[r]+sum[r-it.s.f]+(it.f+it.s.f-1)*(r-it.s.f);
        }
        else{
            ll r=*found.lower_bound(it.s.f); found.insert(it.s.f);
            track[it.s.f]=track[r]+sum[r-it.s.f]+(it.f+it.s.f-1)*(r-it.s.f);
        }
    }
    for(ll i=1;i<=q;i++){
        cout<<ans[i]<<"\n";
    }
}  

#include <bits/stdc++.h>   
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long  
const ll INF_MUL=1e13;
const ll INF_ADD=1e18;  
#define pb push_back               
#define mp make_pair        
#define nline "\n"                         
#define f first                                          
#define s second                                             
#define pll pair<ll,ll> 
#define all(x) x.begin(),x.end()   
#define vl vector<ll>         
#define vvl vector<vector<ll>>    
#define vvvl vector<vector<vector<ll>>>          
#ifndef ONLINE_JUDGE    
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);  
#endif     
const ll MOD=1e9+7;     
const ll MAX=100010;   
ll cal(ll n){
    ll now=(n*(n+1))/2;      
    return now; 
} 
class ST {
public:
    vector<ll> segs;
    ll size = 0;
    ll ID = INF_ADD;
 
    ST(ll sz) {
        segs.assign(2 * sz, ID);  
        size = sz;  
    }   
      
    ll comb(ll a, ll b) {
        return min(a, b);  
    }
 
    void upd(ll idx, ll val) {
        segs[idx += size] = val;
        for(idx /= 2; idx; idx /= 2) segs[idx] = comb(segs[2 * idx], segs[2 * idx + 1]);
    }
 
    ll query(ll l, ll r) {
        ll lans = ID, rans = ID;  
        for(l += size, r += size + 1; l < r; l /= 2, r /= 2) {
            if(l & 1) lans = comb(lans, segs[l++]);
            if(r & 1) rans = comb(segs[--r], rans);
        }
        return comb(lans, rans);
    }
};  
void solve(){  
    ll n; cin>>n;
    vector<ll> a(n+5,0),use(n+5,0),pref(n+5,0);
    for(ll i=1;i<=n;i++){
        cin>>a[i];  
        use[i]=min(use[i-1]+1,a[i]); pref[i]=pref[i-1]+use[i]; 
    }
    ST segtree(n+5);  
    auto get=[&](ll l,ll r,ll till,ll pos,ll tar){
        while(l<=r){
            ll mid=(l+r)/2;     
            if(segtree.query(pos,mid)>=tar){     
                till=mid,l=mid+1;  
            }     
            else{
                r=mid-1;         
            }  
        }  
        return till;        
    };        
    vector<ll> track(n+5,0);         
    for(ll i=n;i>=1;i--){   
        segtree.upd(i,a[i]-i); ll till=get(i,n,i,i,a[i]-i);  
        track[i]=track[till+1]+cal(a[i]+till-i)-cal(a[i]-1); 
    }
    ll q; cin>>q;
    while(q--){
        ll p,x; cin>>p>>x; ll target=min(x,use[p-1]+1);
        ll till=get(p+1,n,p,p+1,target-p);
        ll ans=pref[p-1]+track[till+1]+cal(target+till-p)-cal(target-1);
        cout<<ans<<nline;
    }
    return;
}                 
int main()                                                                           
{                     
    ios_base::sync_with_stdio(false);                           
    cin.tie(NULL);                         
    #ifndef ONLINE_JUDGE               
    freopen("input.txt", "r", stdin);                                           
    freopen("output.txt", "w", stdout);  
    freopen("error.txt", "w", stderr);                        
    #endif    
    ll test_cases=1;                   
    //cin>>test_cases;
    while(test_cases--){   
        solve();     
    }
    cout<<fixed<<setprecision(10);
    cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 
} 

It is easy to see that a necessary condition for a solution to exist is that the number of $$$1$$$ in $$$s$$$ should be even. It turns out that this condition is sufficient too.

Here is one valid construction:

We make $$$n$$$ pairs of the form $$$(s[2i-1],s[2i])$$$ for $$$(1 \leq i \leq n)$$$.

Assume we have $$$x$$$ pairs in which both elements are different and $$$n-x$$$ pairs in which both elements are same.

\textbf{Claim} — $$$x$$$ should be even.

\textbf{Proof} — Assume that among the $$$n-x$$$ pairs in which both elements are same, we have $$$y$$$ pairs in which both elements are $$$1$$$. So number of $$$1$$$ in $$$s$$$ is $$$x+2 \cdot y$$$. We know that number of $$$1$$$ in $$$s$$$ is even, so for $$$x+2 \cdot y$$$ to be even, $$$x$$$ should also be even.

Now we will select $$$x$$$ indices; exactly one index from each of the $$$x$$$ pairs in which both elements are distinct. Take the index of $$$0$$$ from $$$i_{th}$$$ pair if $$$i$$$ is odd, else take the index of $$$1$$$. Thus our selected characters = $$${0,1,0,1, \dots ,0,1}$$$

Now on cyclically shifting the selected characters clockwise once, we can see that elements at selected indices got flipped.

Since, elements in those $$$x$$$ pairs were distinct initially, and we flipped exactly one character from each of those $$$x$$$ pairs, both elements of those $$$x$$$ pairs are same now.

Hence, in updated $$$s$$$, $$$s[2i-1]=s[2i]$$$.

So, for $$$s_1$$$, we can select characters of all odd indices.

Finally we'll have $$$s_1 = s_2$$$. Time complexity is $$$O(n)$$$.

#include <bits/stdc++.h>     
using namespace std;
#define ll long long
void solve(){
    ll n; cin>>n;
    string s; cin>>s;
    ll freq=0;
    vector<ll> ans;
    ll need=0;
    for(ll i=0;i<2*n;i+=2){
        if(s[i]!=s[i+1]){
            freq++;
            ans.push_back(i+1);
            if(s[i]-'0'!=need){
                ans.back()++;
            }
            need^=1;
        }
    }
    if(freq&1){
        cout<<"-1\n";
        return;
    }
    cout<<ans.size()<<" ";
    for(auto it:ans){
        cout<<it<<" ";
    }
    cout<<"\n";
    for(ll i=1;i<=2*n;i+=2){
        cout<<i<<" \n"[i+1==2*n];
    }
}
int main()                                                                                
{  
    ios_base::sync_with_stdio(false);                         
    cin.tie(NULL);  
    ll t; cin>>t;
    while(t--){
        solve();
    }
}  

As the constraints suggest, we should use dp to solve this problem.

Let's write the original indices of the array that are added during this process — $$$p_1, p_2, \ldots, p_n$$$. None of added numbers are zeroed in an optimal answer. It gives that $$$p_1 \le p_2 \le \ldots \le p_n$$$ and the answer is equal to the sum of $$$a[p_k]$$$ ($$$1 \leq k \leq n$$$).

To get the optimal answer we'll use $$$dp[t][last][m]$$$ = maximum score on $$$t$$$-th turn if $$$p_t = last$$$ and we have performed $$$m$$$ swapping moves (the first dimension can be omitted). Note that $$$m \leq i$$$. It can be updated by considering the next index but it will take $$$O(n^4)$$$. The most straightforward way to improve it to $$$O(n^3)$$$ is to use prefix maximums.

Here are some details.

We have only two cases:

1. $$$p_t=p_{t-1}$$$ — In this case, our transition is just $$$dp[t][last][m]=dp[t-1][last][m-1]+a[last]$$$

2. $$$p_t > p_{t-1}$$$ — Let us make some observations. First of all, $$$p_t \ge t$$$. So number of swaps to bring $$$p_t$$$ to index $$$t$$$ is fixed. It is $$$p_t-t$$$. So $$$dp[t][last][m]=\max_{j=1}^{last-1} (dp[t-1][j][m-(p_t-t)])+a[last]$$$. Note that we can find $$$\max_{j=1}^{last-1} (dp[t-1][j][m-(p_t-t)])$$$ in $$$O(1)$$$. Hint — use prefix maximum.

Time complexity is $$$O(n^3)$$$.

#include <bits/stdc++.h>   
using namespace std;
const int MAX=505; 
vector<vector<vector<int>>> dp(MAX,vector<vector<int>>(MAX,vector<int>(MAX,-(int)(1e9))));
int main()                                                                          
{                        
    int n; cin>>n;
    vector<int> a(n+5);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    vector<vector<int>> prefix(n+5,vector<int>(n+5,0));
    int ans=0;  
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){ 
            for(int k=0;k<=i;k++){
                if(k){ 
                    dp[i][j][k]=dp[i-1][j][k-1]+a[j];
                }
                if(j>=i){
                    int need=j-i;
                    if(need>k){
                        continue;
                    }
                    dp[i][j][k]=max(dp[i][j][k],prefix[k-need][j-1]+a[j]); 
                }
            }
        }
        for(int j=1;j<=n;j++){
            for(int k=0;k<=i;k++){
                prefix[k][j]=max(prefix[k][j],dp[i][j][k]); 
            }
        }
        for(int j=0;j<=i;j++){
            for(int k=1;k<=n;k++){
                prefix[j][k]=max(prefix[j][k],prefix[j][k-1]);
                ans=max(ans,prefix[j][k]);
            }
        }
    }
    cout<<ans;
}