#include "bits/stdc++.h"

using namespace std;


    class Queue{
    public:
        unsigned long long N_op = 0;
        Queue(int size) : length(size), arr(new int[size]), begin(0), count(0), end(-1){ N_op+=7; }
        ~Queue(){ delete []arr; N_op++;}
        void push(int el){
            if(isFull())
                resize(length + length / 10);
            ++end%=length;
            arr[end] = el;
            count++;
            N_op+=8;
        }
        void pop(){
            if(!isEmpty()){
                arr[begin] = INT_MIN;
                ++begin%=length;
                count--;
            } else {
                throw runtime_error("going beyond the boundaries of the array");
            }
            N_op+=8;
        }
        int front(){
            if(!isEmpty())
                return arr[begin];
            else throw runtime_error("going beyond the boundaries of the array");
            N_op+=5;
        }
        void resize(int new_size){
            int *arr2 = arr;
            arr = new int[new_size];
            for(int i = 0; i < length; ++i){
                arr[i] = arr2[(i + begin) % length];
            }
            begin = 0;
            end = length - 1;
            length = new_size;
            delete []arr2;
            N_op+=4*length + 13;
        }
        bool isEmpty(){ return size() == 0; N_op+=2; }
        bool isFull() { return size() == count; N_op+=2; }
        int size() { return length; N_op++; }


        void print(){
            for(int i = begin; i < begin + count; ++i)
                cout << arr[i%length] << ' ';
            cout << endl;
        }



    private:
        int *arr;
        int length;
        int begin;
        int end;
        int count;
    };
void sort(Queue& q){
    q.N_op+=3;
    for(int i = 0; i < q.size(); ++i){
        q.N_op+= 12;
        int mn = INT_MAX;
        int first = 0, temp = 0;
        bool swap = true;
        for(int j = 0; j < i; ++j){
            q.N_op++;
            temp = q.front();
            q.pop();
            q.push(temp);
        }
        first = q.front();
        for(int j = i; j < q.size(); ++j){
            temp = q.front();
            mn = min(q.front(), mn);
            q.pop();
            q.push(temp);
            q.N_op+=3;
        }
        for(int j = 0; j < i; ++j){
            q.N_op++;
            temp = q.front();
            q.pop();
            q.push(temp);
        }
        for(int j = i; j < q.size(); ++j){
            q.N_op+=5;
            temp = q.front();
            q.pop();
            if(temp == mn && swap) {
                q.push(first);
                swap = false;
            }
            else if(i == j) {
                q.push(mn);
            }
            else
                q.push(temp);
        }
    }
}

int main(){
    for (int a = 5000; a <= 10000; a += 500) {
        size_t n = 0;
        Queue queue(a);
        srand(time(NULL));
        ::clock_t start = ::clock();
        for(int i = 0; i < a; ++i)
            queue.push(::rand() % (5 * a));
        cout << "init of " << a << " elements takes " <<
             (::clock() - start) * 1000 /CLOCKS_PER_SEC << " millisec\n";
        start = ::clock();
        sort(queue);
        cout << "sort of " << a << " elements takes " <<
             (::clock() - start) * 1000 /CLOCKS_PER_SEC << " millisec\n";
        cout << "takes " << queue.N_op << " N_op\n\n";
    }

}