# Make binary search dynamic
###### tags: `學業/工作`
Accepted
Time: 3ms Memory: 3MB Lang: C++ Author: 110502518

#include<bits/stdc++.h>
using namespace std;
int logN = 15;
int N = (int) (pow(2, logN) + 0.5);
int n = N;



struct element{
    int val;
    bool mark;
    bool operator < (const element& rhs){return val < rhs.val;}
};
//bool operator < (const element& a, const element& b) return a.val < b.val;

vector<vector<element>> Vectors;
vector<bool> is_full;
vector<int> mark_counter;

pair<int, int> search_result;

void init(){
    Vectors = vector<vector<element>>(logN);
    is_full = vector<bool>(logN, false);
    mark_counter = vector<int>(logN, 0);
    for(int i = 0; i < logN; i++){
        Vectors[i] = vector<element>();
    }
}

void Merge(vector<element>& v1, vector<element>& v2){
    int i = 0, j = 0;
    vector<element> v3;
    while (i < v1.size() && j < v2.size()){
        if (v1[i] < v2[j]) v3.push_back(v1[i++]);
        else v3.push_back(v2[j++]);
    }
    while (i < v1.size()) v3.push_back(v1[i++]);
    while (j < v2.size()) v3.push_back(v2[j++]);
    v1 = v3;
}

void Print(){
    for(int tt=0; tt< Vectors.size(); tt++){
        for(int t = 0; t<Vectors[tt].size(); t++){
            if (Vectors[tt][t].mark) cout << Vectors[tt][t].val << " ";
            else cout << "-" << " ";
        }
        cout << "\n";
    }
    cout << "is_full: ";
    for (int i = 0; i < is_full.size(); i++) cout << is_full[i] << " ";
    cout << "\nmark_counter: ";
    for (int i = 0; i < mark_counter.size(); i++) cout << mark_counter[i] << " ";
    cout << "\n";
}

pair<int, int> Search(int obj){
    element obj_ele = element{obj, true};
    for (int i=0; i<Vectors.size(); i++){
        if (is_full[i]){
            int lb = lower_bound(Vectors[i].begin(), Vectors[i].end(), obj_ele) - Vectors[i].begin();
            if (lb < Vectors[i].size() && Vectors[i][lb].val == obj){
                return {i, lb};
            }
        }
    }
    return {-1, -1};
}

bool Delete(int obj){
    search_result = Search(obj);
    if (search_result.first == -1 || !Vectors[search_result.first][search_result.second].mark){
        return false;
    }
    if (search_result.first == 0){
        Vectors[0] = vector<element>();
        is_full[0] = false;
        return true;
    }
    Vectors[search_result.first][search_result.second].mark = false;
    if (++mark_counter[search_result.first] >= int(Vectors[search_result.first].size()/2)){
        if (is_full[search_result.first-1]){
            vector<element> tmp;
            for(element x: Vectors[search_result.first]){
                if (x.mark) tmp.push_back(x);
            }
            Merge(tmp, Vectors[search_result.first-1]);
            Vectors[search_result.first] = tmp;
            Vectors[search_result.first-1] = vector<element>();
            is_full[search_result.first] = true;
            is_full[search_result.first-1] = false;
            mark_counter[search_result.first] = mark_counter[search_result.first-1];
            mark_counter[search_result.first-1] = 0;
        }
        else{
            for(element x: Vectors[search_result.first]){
                if (x.mark) Vectors[search_result.first-1].push_back(x);
            }
            Vectors[search_result.first] = vector<element>();
            is_full[search_result.first] = false;
            is_full[search_result.first-1] = true;
            mark_counter[search_result.first] = 0;
            mark_counter[search_result.first-1] = 0;
        }
    }
    return true;
}

bool Insert(int obj){
    search_result = Search(obj);
    if (search_result.first != -1){
        if(Vectors[search_result.first][search_result.second].mark){
            return false;
        }
        else{
            Vectors[search_result.first][search_result.second].mark = true;
            return true;
        }
    }
    element new_ele = element{obj, true};
    int i = 0;
    while(is_full[i]) i++;
    if(i == logN+1){ // is full
        return false;
    }
    vector<element> tmp = vector<element>();
    for(int j=0; j<i; j++){
        Merge(tmp, Vectors[j]);

        Vectors[j] = vector<element>();
        is_full[j] = false;

        mark_counter[i] += mark_counter[j];
        mark_counter[j] = 0;
    }
    is_full[i] = true;
    tmp.insert(lower_bound(tmp.begin(), tmp.end(), new_ele), new_ele);
    Vectors[i] = tmp;
    return true;
}
int test, value;
string command;
vector<int> input;

int main(){

    cin >> n;

    init();

    for(int i = 0; i < n; i++){
        int tmp;
        cin >> tmp;
        input.push_back(tmp);
    }
    cin >> test;

    N = n + test;
    logN = (int) (log2(N+test) + 0.5) + 1;
    init();
    for (int i = 0; i < n; i++){
        Insert(input[i]);
    }

    while(test--){
        cin >> command >> value;
        if (command == "s"){
            search_result = Search(value);
            if (search_result.first != -1 && Vectors[search_result.first][search_result.second].mark){
                cout << "Found\n";
            }
            else{
                cout << "Not Found\n";
            }
        }
        else if (command == "d"){
            if (Delete(value)){
                cout << "Delete Success\n";
            }
            else{
                cout << "Delete Failed\n";
            }
        }
        else if (command == "i"){
            if (Insert(value)){
                cout << "Insert Success\n";
            }
            else{
                cout << "Insert Failed\n";
            }
        }
    }
}