Hope you liked the problems!

1856A - Сказка о сортировке

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define gsize(x) (int)((x).size())

const char nl = '\n';
typedef long long ll;
typedef long double ld;

using namespace std;

void solve() {
    int n;
    cin >> n;
    
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    
    int ans = 0;
    for (int i = 0; i < n - 1; i++) {
        if (a[i] > a[i + 1]) {
            ans = max(ans, a[i]);
        }
    }
    
    cout << ans << nl;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
    
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
}

1856B - Хорошие массивы

include <bits/stdc++.h>

define all(x) (x).begin(), (x).end()

define allr(x) (x).rbegin(), (x).rend()

define gsize(x) (int)((x).size())

const char nl = '\n'; typedef long long ll; typedef long double ld;

using namespace std;

void solve() { int n; cin >> n;

vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];

ll sum_a = 0, cnt_1 = 0;
for (int x: a) {
    sum_a += x;
    if (x == 1) cnt_1++;
}

if (sum_a >= cnt_1 + n && n > 1) {
    cout << "YES" << nl;
} else {
    cout << "NO" << nl;
}

}

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

int T;
cin >> T;
while (T--) {
    solve();
}

} ~~~~~

1856C - Стать максимумом

include <bits/stdc++.h>

define all(x) (x).begin(), (x).end()

define allr(x) (x).rbegin(), (x).rend()

define gsize(x) (int)((x).size())

const char nl = '\n'; typedef long long ll; typedef long double ld;

using namespace std;

void solve() { ll n, k; cin >> n >> k;

vector<ll> a(n);
for (int i = 0; i < n; i++) cin >> a[i];

ll lb = 0, ub = *max_element(all(a)) + k, ans = 0;
while (lb <= ub) {
    ll tm = (lb + ub) / 2;
    bool good = false;

    for (int i = 0; i < n; i++) {
        vector<ll> min_needed(n);
        min_needed[i] = tm;

        ll c_used = 0;
        for (int j = i; j < n; j++) {
            if (min_needed[j] <= a[j]) continue;

            if (j + 1 >= n) {
                c_used = k + 1;
                break;
            }

            c_used += min_needed[j] - a[j];
            min_needed[j + 1] = max(min_needed[j + 1], min_needed[j] - 1);
        }

        if (c_used <= k) good = true;
    }

    if (good) {
        ans = tm;
        lb = tm + 1;
    } else {
        ub = tm - 1;
    }
}

cout << ans << nl;

}

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

int T;
cin >> T;
while (T--) solve();

} ~~~~~

1856D - Более неправильно

include <bits/stdc++.h>

define all(x) (x).begin(), (x).end()

define allr(x) (x).rbegin(), (x).rend()

define gsize(x) (int)((x).size())

const char nl = '\n'; typedef long long ll; typedef long double ld;

using namespace std;

int query(int l, int r) { if (l == r) return 0; cout << "? " << l << ' ' << r << endl;

int res;
cin >> res;
return res;

}

// Finds max on p[l; r] int solve(int l, int r) { if (l == r) return l;

int m = (l + r) / 2;
int a = solve(l, m);
int b = solve(m + 1, r);

int r1, r2;
r1 = query(a, b - 1);
r2 = query(a, b);

if (r1 == r2) {
    return b;
} else {
    return a;
}

}

void solve() { int n; cin >> n;

int ans = solve(1, n);
cout << "! " << ans << endl;

}

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

int T;
cin >> T;
while (T--) {
    solve();
}

} ~~~~~

1856E1 - ПерестановДерево (простая версия)

include <bits/stdc++.h>

define all(x) (x).begin(), (x).end()

define allr(x) (x).rbegin(), (x).rend()

define gsize(x) (int)((x).size())

const char nl = '\n'; typedef long long ll; typedef long double ld;

using namespace std;

const int maxn = 1000000;

vector g[maxn]; int s[maxn]; ll ans = 0;

void dfs(int v, int p = -1) { vector a; s[v] = 1;

for (int u: g[v]) {
    if (u == p) continue;
    dfs(u, v);
    s[v] += s[u];

    a.push_back(s[u]);
}

vector<ll> dp(s[v]);
ll cs = 0;
for (int x: a) {
    for (ll i = cs + x; i >= 0; i--) {
        for (ll pr = min(cs, i); pr >= max(0LL, i - x); pr--) {
            ll j = i - pr;
            dp[i] = max(dp[i], dp[pr] + j * (cs - pr) + pr * (x - j));
        }
    } 
    cs += x;
}

ans += *max_element(all(dp));
dp.clear();
a.clear();

}

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

int n;
cin >> n;
for (int i = 1; i < n; i++) {
    int x;
    cin >> x;
    g[x - 1].push_back(i);
}

dfs(0);

cout << ans << nl;

} ~~~~~

1856E2 - ПерестановДерево (сложная версия)

include <bits/stdc++.h>

define all(x) (x).begin(), (x).end()

define allr(x) (x).rbegin(), (x).rend()

define gsize(x) (int)((x).size())

const char nl = '\n'; typedef long long ll; typedef long double ld;

using namespace std;

const int maxn = 1000000;

vector g[maxn]; int s[maxn]; ll ans = 0; vector b; ll closest;

template void subset_sum(int n) { if (n >= len) { subset_sum<std::min(len*2, maxn)>(n); return; }

bitset<len> dp;

dp[0] = 1;
for (ll x: b) {
    dp = dp | (dp << x);
}

ll cv = n;
closest = 0;
for (int i = 0; i <= n; i++) {
    if (dp[i] && abs(i - (n - i)) < cv) {
        closest = i;
        cv = abs(i - (n - i));
    }
}

}

ll solve(vector &a) { if (a.empty()) return 0;

sort(allr(a));
ll cs = 0;
for (ll x: a) cs += x;

if (a[0] * 2 >= cs) {
    return a[0];
}

int n = gsize(a);
a.push_back(0);

b.clear();
int pi = 0;
for (int i = 1; i <= n; i++) {
    if (a[i] != a[i - 1]) {
        ll cnt = i - pi;
        ll x = a[i - 1];

        ll j = 1;
        while (j < cnt) {
            b.push_back(x * j);
            cnt -= j;
            j *= 2;
        }            
        b.push_back(x * cnt);

        pi = i;
    }
}

subset_sum(cs);
return closest;

}

void dfs(int v, int p = -1) { vector a; s[v] = 1;

for (int u: g[v]) {
    if (u == p) continue;
    dfs(u, v);
    s[v] += s[u];

    a.push_back(s[u]);
}

ll x = solve(a);
ans += x * (s[v] - 1 - x);
a.clear();

}

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

int n;
cin >> n;
for (int i = 1; i < n; i++) {
    int x;
    cin >> x;
    g[x - 1].push_back(i);
}

dfs(0);

cout << ans << nl;

} ~~~~~