Seriously?

Solution with O(n * m * logn) complexity is too slow? Probably we should sort faster?

Let's elaborate, when a segment can become a train carriage.

Try to use dynamic programming on prefix.

Try to solve problem, when buttons can't be broken.

Try to find out whether the buttons are broken somehow, without taking risk of losing.

Try to use interval tree.

int n, k, s = 0;
cin >> n >> k;
for (int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    s += x;
}
for (int ans = 0;; ans++) {
    int a = 2 * (s + ans * k);
    int b = (2 * k - 1) * (ans + n);

    if (a >= b) {
        cout << ans;
        return 0;
    }
}

for (int i = 0; i < n; i++) {
    cin >> k[i] >> l[i];
    a.push_back(make_pair(min(2 * k[i], l[i]) - min(k[i], l[i]), i));
}
sort(a.rbegin(), a.rend());

long long ans = 0;
for (int i = 0; i < f; i++) {
    int pos = a[i].second;
    ans += min(2 * k[pos], l[pos]);
}
for (int i = f; i < n; i++) {
    int pos = a[i].second;
    ans += min(k[pos], l[pos]);
}
cout << ans;

st[0] = 1;
for ( int j = 1; j < maxn; j++ )
    st[j] = ( 2 * st[j - 1] ) % base;
int n;
scanf ( "%d", &n );
for ( int j = 0; j < n; j++ )
    scanf ( "%d", &a[j] );
sort( a, a + n );
int ans = 0;
for ( int j = 1; j < n; j++ ) {
    int len = a[j] - a[j - 1];
    int cntL = j;
    int cntR = n - j;
    int add = ( 1LL * ( st[cntL] - 1 + base ) * ( st[cntR] - 1 + base ) ) % base;
    ans = ( 1LL * ans + 1LL * len * add ) % base;
}
printf ( "%d\n", ans );

int query(int x,int y){
    if(x==-1)return 0;
    cout<<1<<' '<<x<<' '<<y<<endl;
    string ret;
    cin>>ret;
    return ("TAK"==ret);
}

int get(int l,int r){
    if(l>r)return -1;

    while(l<r){
        int m=(l+r)/2;
        if(query(m,m+1)){
            r=m;
        }else l=m+1;
    }
    return l;
}

int main() {
    int n,k;
    cin>>n>>k;

    int x=get(1,n);
    int y=get(1,x-1);
    if(!query(y,x))y=get(x+1,n);
    cout<<2<<' '<<x<<' '<<y<<endl;

    return 0;
}

ll dp[32][2][2][2];
ll sum[32][2][2][2];

void add(ll &x,ll y){
    x+=y;
    if(x>=mod)x-=mod;
}

void sub(ll &x,ll y){
    x-=y;
    if(x<0)x+=mod;
}

ll mul(ll x,ll y){
    return x*y%mod;
}

ll pot[32];

ll solve(int x,int y,int z){
    if(x<0||y<0||z<0)return 0;
    memset(dp,0,sizeof dp);
    memset(sum,0,sizeof sum);
    vi A,B,C;
    rep(j,0,31){
        A.pb(x%2);x/=2;
        B.pb(y%2);y/=2;
        C.pb(z%2);z/=2;
    }
    reverse(all(A));
    reverse(all(B));
    reverse(all(C));
    dp[0][1][1][1]=1;
    sum[0][1][1][1]=0;
    rep(i,0,31){
        rep(a,0,2)rep(b,0,2)rep(c,0,2){
            rep(x,0,2)rep(y,0,2){
                int z=x^y;
                if(a==1&&A[i]==0&&x==1)continue;
                if(b==1&&B[i]==0&&y==1)continue;
                if(c==1&&C[i]==0&&z==1)continue;
                add(dp[i+1][a&(A[i]==x)][b&(B[i]==y)][c&(C[i]==z)],dp[i][a][b][c]);
                add(sum[i+1][a&(A[i]==x)][b&(B[i]==y)][c&(C[i]==z)],sum[i][a][b][c]);
                add(sum[i+1][a&(A[i]==x)][b&(B[i]==y)][c&(C[i]==z)],mul(z<<(30-i),dp[i][a][b][c]));

            }
        }
    }
    ll res=0;
    rep(a,0,2)rep(b,0,2)rep(c,0,2){
        add(res,sum[31][a][b][c]);
        add(res,dp[31][a][b][c]);
    }
    return res;
}

int main(){
    int T;
    cin>>T;
    while(T--){
        int x,y,x2,y2,k;
        cin>>x>>y>>x2>>y2>>k;
        --x;--y;--x2;--y2;--k;
        ll res=0;
        add(res,solve(x2,y2,k));
        sub(res,solve(x2,y-1,k));
        sub(res,solve(x-1,y2,k));
        add(res,solve(x-1,y-1,k));
        cout<<res<<'\n';
    }
    return 0;
}

struct node {
    int prior, sz, dp, add;
    node *l, *r;
    node ( int x ) {
        prior = ( rand() << 15 ) | rand();
        // sz = 1;
        dp = x;
        l = r = NULL;
        add = 0;
    }
};
 
typedef node * pnode;

void push( pnode T ) {
    T -> dp += T -> add;
    if ( T -> l )
        T -> l -> add += T -> add;
    if ( T -> r )
        T -> r -> add += T -> add;
    T -> add = 0;
}
 
void merge( pnode &T, pnode L, pnode R ) {
    if ( !L ) {
        T = R;
        return;
    }
    if ( !R ) {
        T = L;
        return;
    }
    if ( L -> prior > R -> prior ) {
        push( L );
        merge( L -> r, L -> r, R );
        T = L;
        return;
    }
    push( R );
    merge( R -> l, L, R -> l );
    T = R;
}
 
void split( pnode T, int value, pnode &L, pnode &R ) {
    if ( !T ) {
        L = R = NULL;
        return;
    }
    push( T );
    if ( T -> dp >= value ) {
        split( T -> l, value, L, T -> l );
        R = T;
        return;
    }
    split( T -> r, value, T -> r, R );
    L = T;
}
 
int findBegin( pnode T ) {
    push( T );
    if ( !T -> l )
        return T -> dp;
    return findBegin( T -> l );
}
 
int findMax( pnode T, int n ) {
    if ( !T )
        return 0;
    push( T );
    return findMax( T -> l, n ) + findMax( T -> r, n ) + ( T -> dp <= inf ? 1 : 0 );
}

pair < int, int > a[maxn];
pnode T = new node( 0 );
pnode L = NULL;
pnode M = NULL;
pnode R = NULL;
pnode rubbish = NULL;
 
void solve() {
    int n;
    scanf ( "%d", &n );
    for ( int j = 1; j <= n; j++ )
        scanf ( "%d%d", &a[j].f, &a[j].s );
    for ( int j = 1; j <= n; j++ )
        merge( T, T, new node( inf + j ) );
    for ( int j = 1; j <= n; j++ ) {
        split( T, a[j].f, L, R );
        split( R, a[j].s, M, R );
        if ( M )
            M -> add += 1;
        int cnt = findBegin( R );
        split( R, cnt + 1, rubbish, R );
        merge( T, L, new node( a[j].f ) );
        merge( T, T, M );
        merge( T, T, R );
    }
    printf ( "%d\n", findMax( T, n ) - 1 );
}

#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <numeric>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <vector>
#include <math.h>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>

using namespace std;

typedef long long ll;
typedef long double ld;

template <typename T>
T nextInt() {
    T x = 0, p = 1;
    char ch;
    do { ch = getchar(); } while(ch <= ' ');
    if (ch == '-') {
        p = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return x * p;
}
const int maxN = (int)2e5 + 10;
const int maxL = 17;
const int INF = (int)1e9;
const int mod = (int)1e9 + 7;
const ll LLINF = (ll)1e18 + 5;

int mul(int x, int y) {
    return 1LL * x * y % mod;
}

void add(int &x, int y) {
    x += y;
    if (x >= mod) x -= mod;
}

void sub(int &x, int y) {
    x -= y;
    if (x < 0) x += mod;
}

int n;
vector <int> g[maxN];
vector <int> d[maxN];
vector <int> coefs[maxN];
int phi[maxN];
int inv[maxN];
int a[maxN];

int tmp[maxN];

void productToTmp(int a, int b) {
    for (size_t it = 0; it < d[a].size(); it++) {
        for (size_t jt = 0; jt < d[b].size(); jt++) {
            int x = d[a][it];
            int cx = coefs[a][it];
            int y = d[b][jt];
            int cy = coefs[b][jt];
            add(tmp[x * y], mul(cx, cy));
        }
    }
}

void precalc() {
    inv[1] = 1;
    for (int i = 1; i < maxN; ++i) {
        phi[i] = i;
        if(i > 1) inv[i] = mul(mod - mod / i, inv[mod % i]);
    }
    for (int i = 1; i < maxN; ++i) {
        for (int j = i; j < maxN; j += i) {
            d[j].push_back(i);
            if (j != i) phi[j] -= phi[i];
        }
    }
    for (int i = 1; i < maxN; ++i) {
        coefs[i].resize(d[i].size());
    }
    coefs[1][0] = 1;
    for (int x = 2; x < maxN; x++) {
        if ((int)d[x].size() == 2) {
            coefs[x][0] = 1;
            coefs[x][1] = inv[x - 1];
        } else {
            int lp = d[x][1];
            int z = x;
            while (z % lp == 0) {
                z /= lp;
            }
            for (int y: d[x]) {
                tmp[y] = 0;
            }
            productToTmp(lp, z);
            for (size_t it = 0; it < d[x].size(); it++) {
                coefs[x][it] = tmp[d[x][it]];
            }
        }
    }
}

int nodes[maxN];
int len = 0;
int sz[maxN];
int blocked[maxN];
int level[maxN];
int anc[maxN];

void calc_sizes(int v, int p = -1) {
    nodes[len++] = v;
    sz[v] = 1;
    anc[v] = p;
    for (int x: g[v]){
        if (blocked[x] || x == p) continue;
        calc_sizes(x, v);
        sz[v] += sz[x];
    }
}

int sum_phi[maxN];

int list_len;
int list[maxN];
int depth[maxN];

void get_list(int v, int par = -1, int dpth = 1) {
    list[list_len] = v;
    depth[list_len++] = dpth;
    for (int x: g[v]) {
        if (par == x || blocked[x]) continue;
        get_list(x, v, dpth + 1);
    }
}

int sum[maxN];

int calc(int value) {
    int cur = 0;
    for(size_t i = 0; i < d[value].size(); ++i) {
        int x = d[value][i];
        add(cur, mul(sum_phi[x], coefs[value][i]));
    }
    return mul(cur, phi[value]);
}

int total = 0;

void solve(int root) { //root is a centroid
    for (int i = 0; i < len; ++i) {
        int u = nodes[i];
        int y = a[u];
        for (int x: d[y]) {
            add(sum_phi[x], phi[y]);
        }
    }
    for (int child: g[root]) {
        if (blocked[child]) continue;

        list_len = 0;
        get_list(child, root);
        {
            //excluding everything which can be counted twice
            for(int i = 0; i < list_len; ++i) {
                int u = list[i];
                int y = a[u];
                for(int x: d[y]) {
                    sub(sum_phi[x], phi[y]);
                }
            }
        }
        {
            for (int i = 0; i < list_len; ++i) {
                int u = list[i];
                int d = depth[i];
                int value = a[u];
                add(total, mul(d, calc(value)));
            }
        }
        {
            //including back
            for(int i = 0; i < list_len; ++i) {
                int u = list[i];
                int y = a[u];
                for(int x: d[y]) {
                    add(sum_phi[x], phi[y]);
                }
            }
        }
    }

    //clear
    for (int i = 0; i < len; ++i) {
        int u = nodes[i];
        int y = a[u];
        for (int x: d[y]) {
            sum_phi[x] = 0;
        }
    }
}

void build(int v, int lev) {
    len = 0;
    calc_sizes(v);
    int centroid = -1;
    for (int i = 0; i < len; ++i) {
        int u = nodes[i];
        int maxChildSize = len - sz[u];
        for (int x: g[u]) {
            if (x != anc[u] && !blocked[x]) {
                maxChildSize = max(maxChildSize, sz[x]);
            }
        }
        if (maxChildSize <= len / 2) {
            centroid = u;
        }
    }
    blocked[centroid] = true;
    level[centroid] = lev;
    solve(centroid);

    for (int x: g[centroid]) {
        if (blocked[x]) continue;
        build(x, lev + 1);
    }
}

int main() {

   // freopen("input.txt", "r", stdin);
   // freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(0);
    precalc();
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 1; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        --x; --y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    build(0, 0);

    total = mul(total, inv[n]);
    total = mul(total, inv[n - 1]);
    total = mul(total, 2);

    cout << total << endl;
    return 0;
}

int n, a, b;
string s;
cin >> n >> a >> b >> s;

a--, b--;

cout << ((s[a] - '0') ^ (s[b] - '0'));

int go(ll l, ll r, ll need, int alphSize)
{
    ll m = l + (r - l) / 2LL;
    if (need < m)
        return go(l, m - 1, need, alphSize - 1);
    else if (need > m)
        return go(m + 1, r, need, alphSize - 1);
    else
        return alphSize;
}

void solveABig()
{
    int n;
    ll k;

    cin >> n >> k;
    ll sz = 1;
    for (int i = 1; i < n; i++)
        sz = sz * 2LL + 1LL;
    
    cout << go(1, sz, k, n);
}

int n;
cin >> n;
if (n == 1)
	cout << -1 << endl;
else
	cout << n << ' ' << n + 1 << ' ' << n * (n + 1) << endl;

int a[maxn];
vector<int> g[maxn];

ll sum_subTree[maxn], mx_subTree[maxn];

void dfs1(int v, int p) {
    sum_subTree[v] = a[v];
    mx_subTree[v] = -llinf;
    for (int i = 0; i < g[v].size(); i++) {
        int to = g[v][i];
        if (to == p)
            continue;
        dfs1(to, v);
        sum_subTree[v] += sum_subTree[to];
        mx_subTree[v] = max(mx_subTree[v], mx_subTree[to]);
    }
    mx_subTree[v] = max(mx_subTree[v], sum_subTree[v]);
}

ll ans = -llinf;

void dfs2(int v, int p, ll out) {
    if (out != -llinf)
    ans = max(ans, sum_subTree[v] + out);

    vector<pair<ll, int> > miniset;
    for (int i = 0; i < g[v].size(); i++) {
        int to = g[v][i];
        if (to == p)
            continue;
        miniset.pb(mp(mx_subTree[to], to));
        sort(miniset.rbegin(), miniset.rend());
        if (miniset.size() == 3)
            miniset.pop_back();
    }
    miniset.pb(mp(-llinf, -1));
    for (int i = 0; i < g[v].size(); i++) {
        int to = g[v][i];
        if (to == p)
            continue;
        ll cur = miniset[0].s == to ? miniset[1].f : miniset[0].f;
        dfs2(to, v, max(out, cur));
    }
}

int main() {
    for (int i = 0; i + 1 < n; i++) {
        int u, v;
        read(u, v);
        u--, v--;
        g[u].pb(v);
        g[v].pb(u);
    }

    dfs1(0, -1);
    dfs2(0, -1, -llinf);
    cout << ((ans == -llinf) ? ("Impossible") : to_string(ans));
    return 0;
}

int can(int len) {
    for (int i = 0; i < 8; i++)
        cur[i] = 0;
    for (int i = 0; i <= n; i++)
        for (int j = 0; j < (1 << 8); j++)
            dp[i][j] = -inf;
    dp[0][0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < (1 << 8); j++) {
            if (dp[i][j] == -inf)
                continue;
            for (int k = 0; k < 8; k++) {
                if (j & (1 << k))
                    continue;
                int it = cur[k] + len - 1;
                if (it >= in[k].size())
                    continue;
                amax(dp[in[k][it] + 1][j | (1 << k)], dp[i][j]);
                    
                it++;
                if (it >= in[k].size())
                    continue;
                amax(dp[in[k][it] + 1][j | (1 << k)], dp[i][j] + 1);
            }
        }
        cur[a[i]]++;
    }

    int ans = -inf;
    for (int i = 0; i <= n; i++)
        ans = max(ans, dp[i][(1 << 8) - 1]);
    if (ans == -inf)
        return -1;

    return ans * (len + 1) + (8 - ans) * len;
}

int main() {
    for (int i = 0; i < n; i++) {
        in[a[i]].push_back(i);
    }

    int l = 1, r = n / 8;
    while (r - l > 1) {
        int m = (l + r) >> 1;
        if (can(m) != -1)
            l = m;
        else
            r = m;
    }
    int ans = max(can(l), can(r));
    if (ans == -1) {
        ans = 0;
        for (int i = 0; i < 8; i++)
            if (!in[i].empty())
                ans++;
    }
    cout << ans;
    return 0;
}