template <class T>

T min(T a, T b) {

    return (a > b) ? b : a;

}

 

template <class T>

T max(T a, T b) {

    return (a < b) ? b : a;

}

 

template <class T, int N>

struct Vqs {

 

    Vqs();

 

    unsigned int count();

    bool empty();

    bool full();

    void clear();

    void print();

 

    T& get_front();

    T& get_back();

    T& pop_back();

    void push_back(T v);

    T& pop_front();

 

    void set(int index, T value);

    T& get(int index);

    int insert(int i, T in[], int count);

    int sai(int i, int count, T indata[]);

    int del(int i, int count);

 

    int front;

    int back;

    T data[N];

};

 

template <class T, int N>

void Vqs<T, N>::clear() {

    front = 0;

    back = 0;

}

 

template <class T, int N>

Vqs<T, N>::Vqs() {

    clear();

}

 

template <class T, int N>

bool Vqs<T, N>::empty() {

    return front == back;

}

 

template <class T, int N>

bool Vqs<T, N>::full() {

    return back - front == N;

}

 

template <class T, int N>

unsigned int Vqs<T, N>::count() {

    return back - front;

}

 

template <class T, int N>

void Vqs<T, N>::print() {

 

    int i = 0;

    int end = back - front;

    std::cout << "\n";

 

    while (i < end) {

        std::cout << data[(front + i++) % N] << ", ";

    }

}

 

template <class T, int N>

T& Vqs<T, N>::get_front() {

    return data[front % N];

}

 

template <class T, int N>

T& Vqs<T, N>::get_back() {

    return data[(back - 1) % N];

}

 

template <class T, int N>

T& Vqs<T, N>::get(int index) {

    return data[index];

}

 

template <class T, int N>

void Vqs<T, N>::set(int i, T value) {

    data[(front + i) % N] = value;

}

 

template <class T, int N>

void Vqs<T, N>::push_back(T v) {

 

    if (front + N == back) {

        ++front;

    }

 

    data[back++ % N] = v;

}

 

template <class T, int N>

T& Vqs<T, N>::pop_back() {

 

    assert(front != back);

    return data[--back % N];

}

 

template <class T, int N>

T& Vqs<T, N>::pop_front() {

 

    assert(front != back);

    return data[front++ % N];

}

 

template <class T, int N>

int Vqs<T, N>::sai(int i, int count, T indata[]) {

 

    int after_i = back - front - i;

 

    if (after_i < 0) {

        return 0;

    }

 

    //init

    int b_count, b_after_i, startj, to_delete;

 

    if (count < 0) {

        startj = i - 1;

        to_delete = ::min(after_i, -count);

    }

    else

    {

        startj = ::max(N - count, after_i) - 1;

        b_count = back + count;

        b_after_i = back - after_i;

    }

 

    //process

    int src, dst;

 

    for (int j = startj; j >= 0; --j) {

        if (count < 0) {

            dst = front + to_delete + j;

            src = dst - to_delete;

        }

        else {

            dst = b_after_i + count + j;

            src = dst - count;

        }

        data[dst % N] = data[src % N];

    }

 

    // postprocess

    if (count < 0) {

        front += to_delete;

        return to_delete;

    }

    else {

 

        int front_candidate = b_count - N;

 

        if (front_candidate > front) {

            front = ::min(front_candidate, b_after_i);

        }

 

        back = ::min(b_count, b_after_i + N);

 

        for (int j = 0; j < count; ++j) {

            data[(front + i + j) % N] = indata[j];

        }

 

        return count;

    }

}

 

template <class T, int N>

int Vqs<T, N>::del(int i, int count) {

    return sai(i, -count, nullptr);

}

 

template <class T, int N>

int Vqs<T, N>::insert(int i, T in[], int count) {

    return sai(i, count, in);

}