#include <cstddef>
#include <iostream>

template <class T>
void Copy(const T* buffer_from, size_t count, T* buffer_to) {
    for (size_t i = 0; i < count; ++i) {
        buffer_to[i] = buffer_from[i];
    }
}

template <class T>
void Swap(T& a, T& b) {
    T c = a;
    a = b;
    b = c;
}

template <class T>
class CircularBuffer {
    T* buffer_;
    size_t capacity_;
    size_t begin_;
    size_t end_;
    size_t size_;

    const static int kIncreaseFactor = 2;

    void BufferReallocation(T* buffer, size_t new_cap) {
        delete[] buffer_;
        buffer_ = (new_cap == 0) ? nullptr : new T[new_cap];
        capacity_ = new_cap;
    }

public:
    CircularBuffer()
        : buffer_(nullptr),
          capacity_(0),
          begin_(0),
          end_(0),
          size_(0) {
    }

    explicit CircularBuffer(size_t count) : CircularBuffer() {
        capacity_ = count;
        if (count != 0) {
            buffer_ = new T[count];
        }
    }

    CircularBuffer(const CircularBuffer& other)
        : begin_(other.begin_),
          end_(other.end_),
          size_(other.Size()) {
        BufferReallocation(buffer_, other.Capacity());
    }

    CircularBuffer& operator=(const CircularBuffer& other) {
        if (this == &other) {
            return *this;
        }

        begin_ = other.begin_;
        end_ = other.end_;
        size_ = other.size_;

        BufferReallocation(other.capacity_);
    }

    ~CircularBuffer() {
        delete[] buffer_;
    }

    T& operator[](size_t idx) {
        return buffer_[(begin_ + idx) % Capacity()];
    }

    const T& operator[](size_t idx) const {
        return buffer_[(begin_ + idx) % Capacity()];
    }

    const T& Front() const {
        return buffer_[begin_];
    }

    T& Front() {
        return buffer_[begin_];
    }

    const T& Back() const {
        return buffer_[end_];
    }

    T& Back() {
        return buffer_[end_];
    }

    size_t Size() const {
        return size_;
    }

    size_t Capacity() const {
        return capacity_;
    }

    bool Empty() const {
        return Size() == 0;
    }

    void PushFront(const T& val) {
        if (Empty()) {
            if (Capacity() == 0) {
                Reserve(1);
            }
            begin_ = 0;
            end_ = 0;
        } else {
            if (Size() == Capacity()) {
                Reserve(Capacity() * kIncreaseFactor);
            }
            begin_ = (begin_ - 1 + Capacity()) % Capacity();
        }

        buffer_[begin_] = val;
        ++size_;
    }

    void PushBack(const T& val) {
        if (Empty()) {
            if (Capacity() == 0) {
                Reserve(1);
            }
            begin_ = 0;
            end_ = 0;
        } else {
            if (Size() == Capacity()) {
                Reserve(Capacity() * kIncreaseFactor);
            }
            end_ = (end_ + 1) % Capacity();
        }

        buffer_[end_] = val;
        ++size_;
    }

    void PopBack() {
        if (!Empty()) {
            end_ = (end_ - 1 + Capacity()) % Capacity();
            --size_;
        }
    }

    void PopFront() {
        if (!Empty()) {
            begin_ = (begin_ + 1) % Capacity();
            --size_;
        }
    }

    void Clear() {
        size_ = 0;
        end_ = begin_;
    }

    void Reserve(int new_cap) {
        if (new_cap <= Capacity()) {
            return;
        }

        T* new_buffer = new T[new_cap];
        for (size_t i = 0; i < Size(); ++i) {
            new_buffer[i] = buffer_[(begin_ + i) % Capacity()];
        }

        capacity_ = new_cap;
        begin_ = 0;
        end_ = begin_ + Size() - 1;

        delete[] buffer_;
        buffer_ = new_buffer;
    }

    void Swap(CircularBuffer<T>& other) {
        ::Swap(buffer_, other.buffer_);
        ::Swap(capacity_, other.capacity_);
        ::Swap(begin_, other.begin_);
        ::Swap(end_, other.end_);
        ::Swap(size_, other.size_);
    }
};


#include <cstddef>

template <class T, size_t N>
class Page {
    T buffer_[N];
    size_t size_;
    size_t begin_;

public:
    Page() : size_(0), begin_(0) {
    }

    Page(const Page& other) = default;
    Page& operator=(const Page& other) = default;
    ~Page() = default;

    T& operator[](size_t idx) {
        return buffer_[begin_ + idx];
    }

    const T& operator[](size_t idx) const {
        return buffer_[begin_ + idx];
    }

    const T& Front() const {
        return buffer_[begin_];
    }

    T& Front() {
        return buffer_[begin_];
    }

    const T& Back() const {
        return buffer_[begin_ + size_ - 1];
    }

    T& Back() {
        return buffer_[begin_ + size_ - 1];
    }

    bool Empty() const {
        return Size() == 0;
    }

    size_t Size() const {
        return size_;
    }

    bool Full() const {
        return Size() == N;
    }

    bool IsBack() const {
        return Empty() || (begin_ == 0 && !Full());
    }

    bool IsFront() const {
        return Empty() || (begin_ != 0 && !Full());
    }

    void PushBack(const T& val) {
        if (!IsBack()) {
            return;
        }

        if (Empty()) {
            begin_ = 0;
        }

        buffer_[size_++] = val;
    }

    void PushFront(const T& val) {
        if (!IsFront()) {
            return;
        }

        if (Empty()) {
            begin_ = N;
        }

        buffer_[--begin_] = val;
        ++size_;
    }

    void PopBack() {
        if (Empty()) {
            return;
        }

        --size_;
    }

    void PopFront() {
        if (Empty()) {
            return;
        }

        --size_;
        ++begin_;
    }

    void Clear() {
        size_ = 0;
    }
};


//deque


template <class T>
void swap(T& a, T& b) {
    T tmp = a;
    a = b;
    b = tmp;
}

template <class T>
class Deque {
    const static size_t kPageSize = 100;

    CircularBuffer<Page<T, kPageSize>*> cb_;

public:
    Deque() : cb_() {
    }

    Deque(const Deque& other) : cb_(other.cb_) {
    }

    Deque& operator=(const Deque& other) {
        if (&other == this) {
            return *this;
        }

        ~cb_();
        cb_ = other.cb_;
        return *this;
    }

    ~Deque() {
        for (size_t i = 0; i < cb_.Size(); ++i) {
            delete cb_[i];
        }
    }

    T& operator[](size_t idx) {
        if (idx < cb_.Front()->Size()) {
            return (*cb_.Front())[idx];
        }

        size_t page_idx = (idx - cb_.Front()->Size()) / kPageSize;
        return (*cb_[page_idx + 1])[(idx - cb_.Front()->Size()) % kPageSize];
    }

    const T& operator[](size_t idx) const {
        if (idx < cb_.Front()->Size()) {
            return (*cb_.Front())[idx];
        } else {
            size_t page_idx = (idx - cb_.Front()->Size()) / kPageSize;
            return (*cb_[page_idx + 1])[(idx - cb_.Front()->Size()) % kPageSize];
        }
    }

    size_t Size() const {
        size_t res = 0;
        for (size_t i = 0; i < cb_.Size(); ++i) {
            res += cb_[i]->Size();
        }

        return res;
    }

    void Swap(Deque& other) {
        swap(cb_, other.cb_);
    }

    void PushBack(const T& value) {
        if (cb_.Empty() || !(cb_.Back()->IsBack())) {
            cb_.PushBack(new Page<T, kPageSize>);
        }

        cb_.Back()->PushBack(value);
    }

    void PushFront(const T& value) {
        if (cb_.Empty() || !(cb_.Front()->IsFront())) {
            cb_.PushFront(new Page<T, kPageSize>);
        }

        cb_.Front()->PushFront(value);
    }

    void PopBack() {
        if (cb_.Empty()) {
            return;
        }

        cb_.Back()->PopBack();
        if (cb_.Back->Empty()) {
            delete cb_.Back();
            cb_.PopBack();
        }
    }

    void PopFront() {
        if (cb_.Empty()) {
            return;
        }

        cb_.Front()->PopFront();
        if (cb_.Front()->Empty()) {
            delete cb_.Front();
            cb_.PopFront();
        }
    }

    void Clear() {
        for (size_t i = 0; i < Size(); ++i) {
            delete cb_[i];
        }

        cb_.Clear();
    }
};

#include <iostream>

using namespace std;

int main()
{
    Deque<int> a;

    a.PushFront(2);
    a.PushFront(1);
    a.PushBack(3);

    cout << a[0] << " " << a[1] << " " << a[2];

    return 0;
}