#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
#include "teams.h"

using ll = long long;
using namespace std;

mt19937_64 rnd(13);

namespace treap {
    int rand_size(int n) {
        return rnd() % n;
    }

    struct node {
        ll val = 0;
        int size = 0;

        int left = 0;
        int right = 0;

        node() = default;
        node(ll val) : val(val), size(1) {}
    };

    static constexpr int max_size = 60'000'000;
    static node tree[max_size];

    int size = 1;

    int new_node(ll val) {
        tree[size] = node(val);
        return size++;
    }

    int cp_node(int x) {
        tree[size] = tree[x];
        return size++;
    }

    void pull(int x) {
        tree[x].size = tree[tree[x].left].size + tree[tree[x].right].size + 1;
    }

    pair<int, int> split_by_key(int x, ll k) {
        if (x == 0) {
            return {0, 0};
        }

        x = cp_node(x);

        if (tree[x].val < k) {
            auto [a, b] = split_by_key(tree[x].right, k);
            tree[x].right = a;
            pull(x);
            return {x, b};
        } else {
            auto [a, b] = split_by_key(tree[x].left, k);
            tree[x].left = b;
            pull(x);
            return {a, x};
        }
    }

    pair<int, int> split_by_size(int x, int k) {
        if (x == 0) {
            return {0, 0};
        }

        x = cp_node(x);

        if (tree[tree[x].left].size + 1 <= k) {
            auto [a, b] = split_by_size(tree[x].right, k - 1 - tree[tree[x].left].size);
            tree[x].right = a;
            pull(x);
            return {x, b};
        } else {
            auto [a, b] = split_by_size(tree[x].left, k);
            tree[x].left = b;
            pull(x);
            return {a, x};
        }
    }

    int merge(int a, int b) {
        if (a == 0 || b == 0) {
            return a + b;
        }

        if (rand_size(tree[a].size + tree[b].size) < tree[a].size) {
            a = cp_node(a);
            tree[a].right = merge(tree[a].right, b);
            pull(a);
            return a;
        } else {
            b = cp_node(b);
            tree[b].left = merge(a, tree[b].left);
            pull(b);
            return b;
        }
    }

    ll right(int x) {
        if (tree[x].right != 0) {
            return right(tree[x].right);
        }
        return tree[x].val;
    }

    int insert(int x, ll k) {
        auto [a, b] = split_by_key(x, k);
        return merge(a, merge(new_node(k), b));
    }
}

int n;
vector<int> ti;

void init(int N, int A[], int B[]) {
    n = N;
    vector<vector<ll>> S(n + 1);

    for (int i = 0; i < n; i++) {
        S[A[i]].push_back((ll)B[i] << 32 | i);
    }

    ti.resize(n + 1);

    for (int l = 1; l <= n; l++) {
        ti[l] = ti[l - 1];

        for (ll r : S[l]) {
            ti[l] = treap::insert(ti[l], r);
        }
    }
}

int can(int M, int K[]) {
    using namespace treap;
    size_t before = treap::size;

    map<int, int> CC;

    for (int i = 0; i < M; i++) {
        CC[K[i]] += K[i];
    }

    int cur = 0;

    for (auto [pos, cnt] : CC) {
        auto [x, y] = split_by_key(cur, (ll)pos << 32);
        auto [a, b] = split_by_key(ti[pos], (ll)pos << 32);

        if (tree[b].size - tree[y].size < cnt) {
            return false;
        }

        int l = cnt - 1, r = tree[b].size;
        while (r - l > 1) {
            int m = (l + r) / 2;
            
            int before2 = treap::size;

            int z = split_by_size(b, m).first;
            ll R = right(z);

            int d = split_by_key(y, R + 1).first;
            
            treap::size = before2;

            if (tree[z].size - tree[d].size >= cnt) {
                r = m;
            } else {
                l = m;
            }
        }

        int z = split_by_size(b, r).first;
        ll R = right(z);

        auto [d1, d2] = split_by_key(y, R + 1);

        cur = merge(x, merge(z, d2));
    }

    treap::size = before;
    return true;
}