Tournament: ใครชนะไม่สำคัญ ก้อนที่ถูกยุบสำคัญกว่า

// IOI 2012 "Tournament" (programming.in.th task 2040) - full solution, O((N + C) log N)
//
// Idea:
//   1) The merge structure is independent of the strengths and of the insert position.
//      Every surviving knight represents a contiguous block of INITIAL positions 0..N-1,
//      so round j merges current elements S_j..E_j into one block [A_j, B_j] of initial
//      positions.  A Fenwick tree with find-kth gives A_j, B_j in O(log N) each.
//   2) Treat the late knight as immortal.  Up to and including the first round he loses,
//      the immortal run is identical to the real run, so counting his wins in the immortal
//      run until the first loss is exactly the answer.
//   3) Inserting him at position p means he occupies initial position p.  He takes part in
//      round j iff p is in [A_j, B_j], and (during the prefix before his first loss) he wins
//      iff no knight stronger than R sits anywhere in [A_j, B_j] other than himself, i.e.
//      iff sum f[A_j .. B_j - 1] == 0 where f[i] = (K[i] > R).  That condition does not
//      depend on p, only on the round -> one bit per round.
//   4) Sweep the rounds in order: a winning round adds +1 to every still-alive p in
//      [A_j, B_j] (range-add / point-query Fenwick), a losing round kills every still-alive
//      p in the range (DSU "next alive" pointer), freezing its answer.  Each p dies once.
#include <bits/stdc++.h>
using namespace std;

namespace fastsol {

struct Fen {
    int n;
    vector<int> t;
    void init(int n_) { n = n_; t.assign(n + 1, 0); }
    void add(int i, int v) { for (++i; i <= n; i += i & -i) t[i] += v; }
    int sum(int i) const { int s = 0; for (++i; i > 0; i -= i & -i) s += t[i]; return s; }
    // 0-indexed k-th set position (assumes it exists)
    int kth(int k) const {
        int pos = 0, rem = k + 1, LOG = 0;
        while ((1 << (LOG + 1)) <= n) ++LOG;
        for (int pw = 1 << LOG; pw > 0; pw >>= 1) {
            if (pos + pw <= n && t[pos + pw] < rem) { pos += pw; rem -= t[pos]; }
        }
        return pos;
    }
};

// returns {best insert position (smallest one achieving the max), max number of wins}
pair<int, int> solve(int N, int C, int R, const vector<int>& K,
                     const vector<pair<int, int>>& rounds,
                     vector<int>* out = nullptr) {
    // ---- 1) block of initial positions merged by each round -------------------
    Fen act;
    act.init(N);
    for (int i = 0; i < N; ++i) act.add(i, 1);
    int cnt = N;
    vector<int> A(C), B(C);
    for (int j = 0; j < C; ++j) {
        int S = rounds[j].first, E = rounds[j].second;
        int a = act.kth(S);
        int b = (E + 1 < cnt) ? act.kth(E + 1) - 1 : N - 1;
        A[j] = a; B[j] = b;
        for (int r = S + 1; r <= E; ++r) act.add(act.kth(S + 1), -1); // absorb the losers
        cnt -= (E - S);
    }

    // ---- 2) per-round win flag ------------------------------------------------
    // pre[i] = number of original knights among K[0..i-1] that are stronger than R
    vector<int> pre(N, 0);                       // K has N-1 entries, so pre has N entries
    for (int i = 0; i + 1 < N; ++i) pre[i + 1] = pre[i] + (K[i] > R ? 1 : 0);
    vector<char> win(C);
    for (int j = 0; j < C; ++j) win[j] = (pre[B[j]] - pre[A[j]] == 0);

    // ---- 3) sweep -------------------------------------------------------------
    Fen diff;                 // range add, point query
    diff.init(N + 1);
    vector<int> nxt(N + 2);   // DSU: next still-alive position >= i
    for (int i = 0; i < N + 2; ++i) nxt[i] = i;
    function<int(int)> find = [&](int x) {
        while (nxt[x] != x) { nxt[x] = nxt[nxt[x]]; x = nxt[x]; }
        return x;
    };
    vector<int> ans(N, -1);

    for (int j = 0; j < C; ++j) {
        int a = A[j], b = B[j];
        if (win[j]) {
            diff.add(a, 1);
            if (b + 1 <= N) diff.add(b + 1, -1);
        } else {
            for (int p = find(a); p <= b; p = find(p + 1)) {
                ans[p] = diff.sum(p);   // frozen at the moment he is knocked out
                nxt[p] = p + 1;         // dead
            }
        }
    }
    for (int p = 0; p < N; ++p) if (ans[p] < 0) ans[p] = diff.sum(p);

    int bestP = 0, bestV = ans[0];
    for (int p = 1; p < N; ++p) if (ans[p] > bestV) { bestV = ans[p]; bestP = p; }
    if (out) *out = ans;
    return {bestP, bestV};
}

} // namespace fastsol

#ifndef STRESS_BUILD
int main() {
    int N, C, R;
    if (scanf("%d %d %d", &N, &C, &R) != 3) return 0;
    vector<int> K(N - 1);
    for (int i = 0; i + 1 < N; ++i) scanf("%d", &K[i]);
    vector<pair<int, int>> rounds(C);
    for (int j = 0; j < C; ++j) scanf("%d %d", &rounds[j].first, &rounds[j].second);
    pair<int, int> r = fastsol::solve(N, C, R, K, rounds);
    printf("%d\n", r.first);
    return 0;
}
#endif

// IOI 2012 "Tournament" - honest brute force oracle.
// For each of the N insert positions, build the explicit line and simulate every round
// literally: scan the range S..E, find the strongest, rebuild the line with only that
// knight kept in the range.  Count a win whenever the late knight is inside the range and
// turns out to be the strongest.  No structure is shared with the fast solution.
#include <bits/stdc++.h>
using namespace std;

namespace brutesol {

pair<int, int> solve(int N, int C, int R, const vector<int>& K,
                     const vector<pair<int, int>>& rounds,
                     vector<int>* out = nullptr) {
    int bestP = -1, bestV = -1;
    if (out) out->assign(N, 0);
    for (int p = 0; p < N; ++p) {
        vector<int> line;
        line.reserve(N);
        for (int i = 0; i < p; ++i) line.push_back(K[i]);
        line.push_back(R);
        for (int i = p; i + 1 < N; ++i) line.push_back(K[i]);

        int wins = 0;
        for (int j = 0; j < C; ++j) {
            int S = rounds[j].first, E = rounds[j].second;
            if (E >= (int)line.size()) { fprintf(stderr, "invalid round\n"); exit(1); }
            int mi = S;
            bool lateHere = false;
            for (int i = S; i <= E; ++i) {
                if (line[i] > line[mi]) mi = i;
                if (line[i] == R) lateHere = true;
            }
            if (lateHere && line[mi] == R) ++wins;
            vector<int> nl;
            nl.reserve(line.size());
            for (int i = 0; i < S; ++i) nl.push_back(line[i]);
            nl.push_back(line[mi]);
            for (int i = E + 1; i < (int)line.size(); ++i) nl.push_back(line[i]);
            line.swap(nl);
        }
        if (out) (*out)[p] = wins;
        if (wins > bestV) { bestV = wins; bestP = p; }
    }
    return {bestP, bestV};
}

} // namespace brutesol

#ifndef STRESS_BUILD
int main() {
    int N, C, R;
    if (scanf("%d %d %d", &N, &C, &R) != 3) return 0;
    vector<int> K(N - 1);
    for (int i = 0; i + 1 < N; ++i) scanf("%d", &K[i]);
    vector<pair<int, int>> rounds(C);
    for (int j = 0; j < C; ++j) scanf("%d %d", &rounds[j].first, &rounds[j].second);
    pair<int, int> r = brutesol::solve(N, C, R, K, rounds);
    printf("%d\n", r.first);
    return 0;
}
#endif