It can be proven that any operation which increases the value of $$$min(a_1, a_2, \dots, a_n)$$$ is unoptimal. Thus, we can take any index $$$m$$$ such that $$$a_m$$$ is the array minimum and use it to increase all other values.

Time complexity: $$$O(n)$$$ or $$$O(nk)$$$ per testcase.

Space complexity: $$$O(n)$$$

// chrono::system_clock::now().time_since_epoch().count()
#include<bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " = " << x << endl;

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = (int)1e3 + 5;

int n, k;
int arr[MAXN];

void solve() {
  scanf("%d %d", &n, &k);
  
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &arr[i]);
  }
  
  int mn = min_element(arr + 1, arr + n + 1) - arr;
  int ans = 0;
  
  for (int i = 1; i <= n; ++i) {
    if (i != mn) {
      while (arr[i] + arr[mn] <= k) {
        arr[i] += arr[mn];
        ++ans;
      }
    }
  }
  
  printf("%d\n", ans);
}

int main() {
  int tt;
  scanf("%d", &tt);
  
  while (tt--) {
    solve();
  }

  return 0;
}

Let us partition the array into three sets $$$X$$$, $$$Y$$$, $$$Z$$$ such that $$$X$$$ contains all numbers less than $$$T/2$$$, $$$Y$$$ contains all numbers equal to $$$T/2$$$ and $$$Z$$$ contains all numbers greater than $$$T/2$$$. It is clear that $$$f(X) = f(Y) = 0$$$. Now, since each pair in $$$Y$$$ makes a sum of $$$T$$$, the best solution is to distribute all numbers in $$$Y$$$ equally among $$$X$$$ and $$$Z$$$.

Time complexity: $$$O(n)$$$

Space complexity: $$$O(n)$$$

#include <bits/stdc++.h>
#define len(v) ((int)((v).size()))
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define chmax(x, v) x = max((x), (v))
#define chmin(x, v) x = min((x), (v))
using namespace std;
using ll = long long;

void solve() {
	int n, tar;
	cin >> n >> tar;
	int curMid = 0;
	for (int i = 0; i < n; ++i) {
		int x; cin >> x;
		int r;
		if (tar % 2 == 0 && x == tar/2)
			r = (curMid++) % 2;
		else if (2*x < tar)
			r = 0;
		else
			r = 1;
		cout << r << " \n"[i==n-1];
	}
}

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

	int nbTests;
	cin >> nbTests;
	for (int iTest = 0; iTest < nbTests; ++iTest) {
		solve();
	}
}

Let's fix some arbitrary number $$$x$$$ and calculate the minimum value of $$$k$$$ such that $$$x$$$ occurs in all segments of length $$$k$$$. Let $$$p_1 < p_2 < \dots < p_m$$$ be the indices of entries of $$$x$$$ in the array. Then, for each $$$1 \le i < m$$$ it is clear that $$$k$$$ should be at least the value of $$$p_{i+1}-p_i$$$. Also, $$$k \ge p_1$$$ and $$$k \ge n - p_m + 1$$$. It is enough to just take the maximum of those values. Let's call this derived value of $$$k$$$ as $$$f(x)$$$.

Now, we can just go in increasing order of $$$x$$$ from $$$1$$$ to $$$n$$$ and try update the suffix $$$[f(x), n]$$$ with $$$x$$$. This can be done straightforwardly, just iterating over the range $$$[f(x), n]$$$. If we arrive at a cell for which the value of $$$x$$$ is already calculated, we immediately terminate our loop and continue our algorithm from $$$x+1$$$.

Time complexity: $$$O(n)$$$. Space complexity: $$$O(n)$$$.

// chrono::system_clock::now().time_since_epoch().count()
#include<bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " = " << x << endl;

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = (int)3e5 + 5;

int f[MAXN], last[MAXN], arr[MAXN], ans[MAXN];
int n;

void solve() {
  scanf("%d", &n);
  
  for (int i = 1; i <= n; ++i) {
    f[i] = last[i] = 0;
    ans[i] = -1;
  }
  
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &arr[i]);
  }
  
  for (int i = 1; i <= n; ++i) {
    int x = arr[i];
    f[x] = max(f[x], i - last[x]);
    last[x] = i;
  }
  
  for (int x = 1; x <= n; ++x) {
    f[x] = max(f[x], n - last[x] + 1);
    
    for (int i = f[x]; i <= n && ans[i] == -1; ++i) {
      ans[i] = x;
    }
  }
  
  for (int i = 1; i <= n; ++i) {
    printf("%d%c", ans[i], " \n"[i == n]);
  }
}

int main() {
  int tt;
  scanf("%d", &tt);
  
  while (tt--) {
    solve();
  }

  return 0;
}

Let $$$S$$$ be the sum of the array. If $$$S$$$ is not divisible by $$$n$$$, then the answer is obviously $$$-1$$$. Otherwise, there always exists a solution which uses no more than $$$3n$$$ queries. We will solve this problem in two phases.

First phase: gather the sum in $$$a_1$$$. Let's iterate over $$$2 \le i \le n$$$ in increasing order. If $$$a_i$$$ is divisible by $$$i$$$, we can immediately transfer it using one operation. Otherwise, we have to make it divisible by transferring $$$i - (a_i \bmod i)$$$ from $$$a_1$$$ to $$$a_i$$$. Note that this operation does not break a condition on non-negativity because all $$$a_i$$$ are initially positive. This way, we successfully finish this phase using at most $$$2n$$$ operations.

Second phase: distribute the sum across all elements. Just iterate over all $$$2 \le i \le n$$$ and make a transfer of $$$S/n$$$ from $$$a_1$$$ to $$$a_i$$$. It takes at most $$$n$$$ operations.

Time complexity: $$$O(n)$$$

Space complexity: $$$O(n)$$$

// chrono::system_clock::now().time_since_epoch().count()
#include<bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " = " << x << endl;

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = (int)1e4 + 5;

vector<array<int, 3>> ans;
int arr[MAXN];
int n;

void go(int x, int y, int z) {
  arr[x] -= x * z;
  arr[y] += x * z;
  ans.pb({x, y, z});
}

void solve() {
  scanf("%d", &n);
  
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &arr[i]);
  }
  
  ans.clear();
  int sum = accumulate(arr + 1, arr + n + 1, 0);
  
  if (sum % n) {
    printf("-1\n");
    return;
  }
  
  for (int i = 2; i <= n; ++i) {
    if (arr[i] % i) {
      go(1, i, i - arr[i] % i);
    }
    
    go(i, 1, arr[i] / i);
  }
  
  for (int i = 2; i <= n; ++i) {
    go(1, i, sum / n);
  }
  
  for (int i = 1; i <= n; ++i) {
    assert(arr[i] == sum / n);
  }
  
  assert((int)ans.size() <= 3 * n);
  printf("%d\n", (int)ans.size());
  
  for (auto &[x, y, z] : ans) {
    printf("%d %d %d\n", x, y, z);
  }
}

int main() {
  int tt;
  scanf("%d", &tt);
  
  while (tt--) {
    solve();
  }

  return 0;
}

#include <bits/stdc++.h>
 
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define ll long long
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)
#define forev(i, b, a) for(int i = (b); i >= (a); --i)
#define VAR(v, i) __typeof( i) v=(i)
#define forit(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
 
using namespace std;
 
const int maxn = (int)4e6 + 100;
const int maxm = (int)1e6 + 100;
const int mod = (int)1e9 + 7;
const int P = (int) 1e6 + 7; 
const double pi = acos(-1.0);
 
#define inf mod
 
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;   
typedef vector<ll> Vll;               
typedef vector<pair<int, int> > vpii;
typedef vector<pair<ll, ll> > vpll;                        

int n, t[2][maxn], id = 1;
ll dp[2][30];
vi g[maxn];

void add(int x, int pos){
	int v = 0;
	forev(i, 29, 0){
		int bit = ((x >> i) & 1);
		if(!t[bit][v]) t[bit][v] = id++;
		v = t[bit][v];
		g[v].pb(pos);	
	}
}
void go(int v, int b = 29){
	int l = t[0][v], r = t[1][v];
	if(l) go(l, b - 1);
	if(r) go(r, b - 1);
	if(!l || !r) return;
	ll res = 0;
	int ptr = 0;
	for(auto x : g[l]){
		while(ptr < sz(g[r]) && g[r][ptr] < x) ptr++;
		res += ptr;
	}
	dp[0][b] += res;
	dp[1][b] += sz(g[l]) * 1ll * sz(g[r]) - res;
}
void solve(){
	scanf("%d", &n);
	forn(i, 1, n){
		int x;
		scanf("%d", &x);
		add(x, i);
	}
	go(0);
	ll inv = 0;
	int res = 0;
	forn(i, 0, 29){
		inv += min(dp[0][i], dp[1][i]);
		if(dp[1][i] < dp[0][i])
			res += (1 << i);
	}
	printf("%lld %d", inv, res);
}
 
int main () {
	int t = 1;
	//scanf("%d", &t);
	while(t--) solve();
}

...

// chrono::system_clock::now().time_since_epoch().count()
#include<bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " = " << x << endl;

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = (int)5e5 + 5;
const int MAXM = (int)3e5 + 5;
const int MAXQ = (int)5e5 + 5;

pii e[MAXM], que[MAXQ], t[MAXN << 2];
vector<int> adj[MAXN];
int tin[MAXN], tout[MAXN], timer;
int par[MAXN], arr[MAXN];
bool del[MAXM];
int n, m, q;

int getPar(int x) {
  if (x == par[x]) {
    return x;
  }
  
  return par[x] = getPar(par[x]);
}

void uni(int a, int b) {
  a = getPar(a);
  b = getPar(b);
  
  if (a == b) {
    return;
  }
  
  ++n;
  par[n] = n;
  par[a] = n;
  par[b] = n;
  adj[n].pb(a);
  adj[n].pb(b);
}

void dfs(int v) {
  tin[v] = ++timer;
  
  for (int to : adj[v]) {
    dfs(to);
  }
  
  tout[v] = timer;
}

pii segMax(int v, int tl, int tr, int l, int r) {
  if (l > r || tl > r || tr < l) {
    return mp(0, 0);
  }
  
  if (l <= tl && tr <= r) {
    return t[v];
  }
  
  int mid = (tl + tr) >> 1;
  int c1 = (v << 1), c2 = (c1 | 1);
  
  return max(segMax(c1, tl, mid, l, r), segMax(c2, mid + 1, tr, l, r));
}

void updPos(int v, int tl, int tr, int p, pii x) {
  if (tl == tr) {
    t[v] = x;
    return;
  }
  
  int mid = (tl + tr) >> 1;
  int c1 = (v << 1), c2 = (c1 | 1);
  
  if (p <= mid) {
    updPos(c1, tl, mid, p, x);
  }
  else {
    updPos(c2, mid + 1, tr, p, x);
  }
  
  t[v] = max(t[c1], t[c2]);
}

void solve() {
  scanf("%d %d %d", &n, &m, &q);
  
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &arr[i]);
  }
  
  for (int i = 1; i <= m; ++i) {
    int u, v;
    scanf("%d %d", &u, &v);
    e[i] = mp(u, v);
  }
  
  for (int i = 1; i <= q; ++i) {
    int a, b;
    scanf("%d %d", &a, &b);
    que[i] = mp(a, b);
    
    if (a == 2) {
      del[b] = 1;
    }
  }
  
  for (int i = 1; i <= n; ++i) {
    par[i] = i;
  }
  
  for (int i = 1; i <= m; ++i) {
    if (!del[i]) {
      uni(e[i].fi, e[i].se);
    }
  }
  
  for (int i = q; i > 0; --i) {
    int tp = que[i].fi;
    
    if (tp == 2) {
      int id = que[i].se;
      uni(e[id].fi, e[id].se);
    }
    else {
      que[i].se = getPar(que[i].se);
    }
  }
  
  for (int i = 1; i <= n; ++i) {
    if (getPar(i) == i) {
      dfs(i);
    }
  }
  
  for (int i = 1; i <= n; ++i) {
    updPos(1, 1, n, tin[i], mp(arr[i], tin[i]));
  }
  
  for (int i = 1; i <= q; ++i) {
    int tp = que[i].fi;
   
    if (tp == 1) {
      int v = que[i].se;
      pii tmp = segMax(1, 1, n, tin[v], tout[v]);
      
      if (tmp.fi == 0) {
        printf("0\n");
      }
      else {
        printf("%d\n", tmp.fi);
        updPos(1, 1, n, tmp.se, mp(0, 0));
      }
    }
  }
}

int main() {
  int tt = 1;
  
  while (tt--) {
    solve();
  }

  return 0;
}

...

#include <bits/stdc++.h>
#define int long long
#define len(v) ((int)((v).size()))
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define chmax(x, v) x = max((x), (v))
#define chmin(x, v) x = min((x), (v))
using namespace std;
using pii = pair<int, int>;

struct EndSet {
	set<int> points;
	pii seg = {1, 0};

	int cbase = 0, cdir = 1;

	void setFree(int mx) {
		points.clear(), cbase = 0, cdir = 1;
		seg = {1, mx};
	}

	void setPush(int x) {
		setFree(0);
		points.insert(x);
	}

	void rotate(int balance) {
		cbase = balance - cbase;
		cdir = -cdir;
		seg = {balance - seg.second, balance - seg.first};
	}

	int tr(int x) {
		return cbase + cdir*x;
	}

	int anti(int x) {
		return cdir * (x - cbase);
	}

	bool in(int x) {
		if (points.count(anti(x)))
			return true;
		return (seg.first <= x && x <= seg.second);	
	}

	void push(int x) {
		points.insert(anti(x));
	}

	void popBelow(int x) {
		seg.second = min(seg.second, x);
		auto nextIt = [&] {
			return (cdir == 1 ? prev(points.end()) : points.begin());
		};
		while (!points.empty() && tr(*nextIt()) > x)
			points.erase(nextIt());
	}
	
	bool empty() {
		return points.empty() && seg.first > seg.second;
	}
};

void solve() {
	int n; cin >> n;
	EndSet util;
	int curAns = 0;
	for (int i = 0; i < n; ++i) {
		int x; cin >> x;
		util.popBelow(x-1); 
		if (x % 2 == 0 && util.in(x/2)) {
			curAns += 2;
			util.setPush(x/2);
		} else if (util.empty()) {
			if (x % 2 == 0)
				curAns += 1, util.setPush(x/2);
			else
				util.setFree(x-1);
		} else {
			curAns += 1;
			if (x % 2 == 0)
				util.push(x/2);
		}
		util.rotate(x);
	}	
	cout << 2*n - curAns << "\n";
}

signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int nbTests;
	cin >> nbTests;
	for (int iTest = 0; iTest < nbTests; ++iTest) {
		solve();
	}
}

...

// chrono::system_clock::now().time_since_epoch().count()
#include<bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " = " << x << endl;

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;

const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const char dc[] = {'R', 'D', 'L', 'U'};
const int INF = (int)1e6;
const int MAXN = (int)3e5 + 5;

namespace {
  struct Edge {
    int v, to, f, c;
    
    Edge() {
      v = to = f = c = 0;
    }
    
    Edge(int v, int to, int c) : v(v), to(to), c(c) {
      f = 0;
    }
  };
  
  vector<Edge> e;
  vector<int> adj[MAXN];
  int ptr[MAXN], d[MAXN], q[MAXN];
  int S, T, newS, newT, V;
  int cap[2][MAXN];
  
  void prep() {
    e.clear();
    
    for (int i = 0; i < V; ++i) {
      adj[i].clear();
      ptr[i] = d[i] = q[i] = 0;
      cap[0][i] = cap[1][i] = 0;
    }
  }
  
  void addEdge(int u, int v, int c) {
    //printf("E %d %d %d\n", u, v, c);
  
    adj[u].pb((int)e.size());
    e.pb(Edge(u, v, c));
    adj[v].pb((int)e.size());
    e.pb(Edge(v, u, 0));
  }
  
  void addEdgeLim(int u, int v) {
    //printf("F %d %d\n", u, v);
    ++cap[0][v];
    ++cap[1][u];
  }
  
  bool bfs() {
    fill(d, d + V, -1);
    d[newS] = 0;
    int l = 0, r = 0;
    q[r++] = newS;
    
    while (l < r) {
      int v = q[l++];
      
      for (int id : adj[v]) {
        if (e[id].f < e[id].c) {
          int to = e[id].to;
          
          if (d[to] == -1) {
            d[to] = d[v] + 1;
            q[r++] = to;
          }
        }
      }
    }
    
    return d[newT] != -1;
  }
  
  int dfs(int v, int flow = INF) {
    if (!flow || v == newT) {
      return flow;
    }
    
    int sum = 0;
    
    for (; ptr[v] < (int)adj[v].size(); ++ptr[v]) {
      int id = adj[v][ptr[v]];
      int to = e[id].to;
      int can = e[id].c - e[id].f;
      
      if (d[to] != d[v] + 1 || can == 0) {
        continue;
      }
      
      int pushed = dfs(to, min(flow, can));
      
      if (pushed > 0) {
        e[id].f += pushed;
        e[id ^ 1].f -= pushed;
        sum += pushed;
        flow -= pushed;
        
        if (flow == 0) {
          return sum;
        }
      }
    }
    
    return sum;
  }
  
  int maxFlow() {
    int ret = 0;
    
    while (bfs()) {
      fill(ptr, ptr + V, 0);
    
      while (int pushed = dfs(newS)) {
        ret += pushed;
      }
    }
    
    return ret;
  }
}

vvi arr, follow;
int n, m;

bool inside(int x, int y) {
  return 0 <= x && x < n && 0 <= y && y < m;
}

int id(int x, int y) {
  return x * m + y;
}

void solve() {
  scanf("%d %d", &n, &m);
  arr = follow = vvi(n, vi(m, -1));
  S = n * m;
  T = S + 1;
  newS = T + 1;
  newT = newS + 1;
  V = newT + 1;
  prep();
  
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      scanf("%d", &arr[i][j]);
    }
  }
  
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      for (int dir = 0; dir < 4; ++dir) {
        int ni = i + dx[dir], nj = j + dy[dir];
        
        if (inside(ni, nj)) {
          if (arr[ni][nj] < arr[i][j]) {
            follow[i][j] = dir;
          }
          else if ((i + j) % 2 == 0 && arr[ni][nj] == arr[i][j]) {
            addEdge(id(i, j), id(ni, nj), 1);
          }
        }
      }
      
      if (follow[i][j] == -1) {
        // important vertex
        if ((i + j) % 2) {
          addEdgeLim(id(i, j), T);
        }
        else {
          addEdgeLim(S, id(i, j));
        }
      }
      else {
        if ((i + j) % 2) {
          addEdge(id(i, j), T, 1);
        }
        else {
          addEdge(S, id(i, j), 1);
        }
      }
    }
  }
  
  for (int i = 0; i <= T; ++i) {
    if (cap[0][i] > 0) {
      addEdge(newS, i, cap[0][i]);
    }
    
    if (cap[1][i] > 0) {
      addEdge(i, newT, cap[1][i]);
    }
  }
  
  addEdge(T, S, INF);
  maxFlow();
  
  for (int id : adj[newS]) {
    if (e[id].f != e[id].c) {
      printf("NO\n");
      return;
    }
  }
  
  vvi ansv, ansc;
  ansv = ansc = vvi(n, vi(m));
  
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      int dir = follow[i][j];
      
      if (dir != -1) {
        int ni = i + dx[dir], nj = j + dy[dir];
        ansv[i][j] = arr[i][j] - arr[ni][nj];
        ansc[i][j] = dir;
      }
    }
  }
  
  for (Edge it : e) {
    int v = it.v, to = it.to;
    
    if (max(v, to) < n * m && it.f == it.c && it.c == 1) {
      int ax = v / m, ay = v % m;
      int bx = to / m, by = to % m;
      ansv[ax][ay] = arr[ax][ay] - 1;
      ansv[bx][by] = 1;
      
      for (int dir = 0; dir < 4; ++dir) {
        if (mp(ax + dx[dir], ay + dy[dir]) == mp(bx, by)) {
          ansc[ax][ay] = dir;
          ansc[bx][by] = (dir + 2) % 4;
        }
      }
    }
  }
  
  printf("YES\n");
  
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      printf("%d%c", ansv[i][j], " \n"[j == m - 1]);
    }
  }
  
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      printf("%c%c", dc[ansc[i][j]], " \n"[j == m - 1]);
    }
  }
}

int main() {
  int tt;
  scanf("%d", &tt);
  
  while (tt--) {
    solve();
  }

  return 0;
}