#include <iostream>
#include <cstring>
#include <iterator>

template<typename T>
class CyclicArray {
 private:
  T* array_;
  size_t size_;

  static int mod(int a, int b) {
    int result = a % b;
    if (result < 0) result += b;
    return result;
  }

 public:
  CyclicArray() : array_(nullptr), size_(0) {}
  CyclicArray(size_t size) {
    try {
      array_ = new T[size]();
      size_ = size;
    } catch (std::bad_alloc& ba) {
      std::cout << ba.what();
    }
  }

  CyclicArray(size_t size, T value) {
    try {
      array_ = new T[size];
      size_ = size;

      for (size_t i = 0; i < size_; i++) {
        array_[i] = value;
      }

    } catch (std::exception& ex) {
      std::cout << ex.what();
    }
  }

  CyclicArray(const CyclicArray& constructor) {
    try {
      array_ = new T[constructor.size_];
      size_ = constructor.size_;

      memcpy(array_, constructor.array_, size_ * sizeof(T));
    } catch (std::bad_alloc& ba) {
      std::cout << ba.what();
    }

    // std::copy(std::begin(constructor.array_), std::end(constructor.array_), std::begin(array_));
  }

  ~CyclicArray() {
    delete[] array_;
  }
  CyclicArray& operator=(const CyclicArray& other) {
    if (array_ == other.array_) {
      return (*this);
    }

    size_ = other.size_;
    delete[] array_;
    array_ = new T[size_];
    memcpy(array_, other.array_, size_ * sizeof(T));
    // std::copy(std::begin(other.array_), std::end(other.array_), std::begin(array_));
    return *this;
  }

  T& operator[](int index) {
    if (size() == 0) {
      throw "IndexError: deque is empty";
    }
    return array_[mod(index, size_)];
  }

  const T& operator[](int index) const {
    if (size() == 0) {
      throw "IndexError: deque is empty";
    }
    return array_[mod(index, size_)];
  }

  size_t size() const {
    return size_;
  }
};

template<typename T>
class Deque {
 private:
  CyclicArray<T> array_;
  size_t size_;
  int first_;

  static const size_t SIZE_CRITICAL = 8;
  static const size_t SIZE_RESERVE = 4;

  template<bool is_const>
  class Iterator:
      public std::iterator<std::random_access_iterator_tag,
                           typename std::conditional<is_const, const T, T>::type, int> {
   private:
    typedef typename std::conditional<is_const, const Deque<T>*, Deque<T>*>::type Deq;
    typedef typename std::conditional<is_const, const T, T>::type output_value_type;

    Deq container_;
    int index_;
   public:
    Iterator() : container_(nullptr), index_(0) {}

    Iterator<is_const>& operator++() {
      ++index_;
      return *this;
    }
    Iterator<is_const> operator++(int) {
      Iterator<is_const> result = (*this);
      ++index_;
      return result;
    }
    Iterator<is_const>& operator--() {
      --index_;
      return *this;
    }
    Iterator<is_const> operator--(int) {
      Iterator<is_const> result = (*this);
      --index_;
      return result;
    }

    Iterator<is_const>& operator+=(int n) {
      index_ += n;
      return *this;
    }
    Iterator<is_const> operator+(int n) const {
      Iterator<is_const> result = (*this);
      result += n;
      return result;
    }
    Iterator<is_const>& operator-=(int n) {
      index_ -= n;
      return *this;
    }
    Iterator<is_const> operator-(int n) const {
      Iterator<is_const> result = (*this);
      result -= n;
      return result;
    }
    int operator-(const Iterator<is_const>& other) const {
      return index_ - other.index_;
    }

    bool operator<=(const Iterator<is_const>& other) const {
      return index_ <= other.index_;
    }
    bool operator>=(const Iterator<is_const>& other) const {
      return index_ >= other.index_;
    }
    bool operator<(const Iterator<is_const>& other) const {
      return index_ < other.index_;
    }
    bool operator>(const Iterator<is_const>& other) const {
      return index_ > other.index_;
    }
    bool operator==(const Iterator<is_const>& other) const {
      return index_ == other.index_;
    }
    bool operator!=(const Iterator<is_const>& other) const {
      return index_ != other.index_;
    }

    output_value_type& operator*() {
      return (*container_)[index_];
    }
    output_value_type& operator[](int n) {
      return (*container_)[index_ + n];
    }
    output_value_type* operator->() {
      return &(operator*());
    }
    Iterator(Deq container, int index) :
        container_(container), index_(index) {}
  };

  void resize(size_t new_size) {
    CyclicArray<T> new_array(new_size);
    for (int i = first_; i < first_ + (int) size_; ++i) {
      new_array[i] = array_[i];
    }
    array_ = new_array;
  }
 public:
  Deque() : array_(CyclicArray<T>(1)), size_(0), first_(0) {}
  Deque(int size, const T& element) {
    size_ = size;
    array_ = CyclicArray<T>(size, element);
    first_ = 0;
  }
  Deque(int size) {
    size_ = size;
    array_ = CyclicArray<T>(size);
    first_ = 0;
  }
  Deque(const Deque& constructor) : array_(constructor.array_), size_(constructor.size_), first_(constructor.first_) {}
  ~Deque() {}

  size_t size() const {
    return size_;
  }
  bool empty() const {
    return size_ == 0;
  }

  void push_back(const T& element) {
    if (array_.size() == 0) {
      resize(1);
    }
    if (size_ == array_.size()) {
      resize(size_ * SIZE_RESERVE);
    }

    array_[first_ + size_] = element;
    ++size_;
  }
  void push_front(const T& element) {
    if (array_.size() == 0) {
      resize(1);
    }
    if (size_ == array_.size()) resize(size_ * SIZE_RESERVE);

    array_[first_ - 1] = element;
    ++size_;
    --first_;
  }
  void pop_back() {
    if (empty()) throw "EmptyError: deque is empty, pop_back failed";
    if (size_ * SIZE_CRITICAL <= array_.size()) resize(size_ * SIZE_RESERVE);

    --size_;
  }
  void pop_front() {
    if (empty()) throw "EmptyError: deque is empty, pop_back failed";
    if (size_ * SIZE_CRITICAL <= array_.size()) resize(size_ * SIZE_RESERVE);

    ++first_;
    --size_;
  }

  T& operator[](int index) {
    //if (index < 0 || index >= (int) size_) throw "IndexError: out of range";
    return array_[first_ + index];
  }
  const T& operator[](int index) const {
    //if (index < 0 || index >= (int) size_) throw "IndexError: out of range";
    return array_[first_ + index];
  }

  T& at(int index) {
    if (index < 0 || index >= static_cast<int>(size())) {
      throw std::out_of_range("AtError: Index is out of range!");
    }
    return array_[first_ + index];
  }

  const T& at(int index) const {
    if (index < 0 || index >= static_cast<int>(size())) {
      throw std::out_of_range("AtError: Index is out of range!");
    }
    return array_[first_ + index];
  }


  typedef Iterator<false> iterator;
  typedef Iterator<true> const_iterator;
  typedef std::reverse_iterator<iterator> reverse_iterator;
  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

  iterator begin() {
    return iterator(this, 0);
  }
  const_iterator begin() const {
    return const_iterator(this, 0);
  }
  const_iterator cbegin() const {
    return const_iterator(this, 0);
  }

  iterator end() {
    return iterator(this, size_);
  }
  const_iterator end() const {
    return const_iterator(this, size_);
  }
  const_iterator cend() const {
    return const_iterator(this, size_);
  }

  reverse_iterator rbegin() {
    return reverse_iterator(end());
  }
  const_reverse_iterator rbegin() const {
    return const_reverse_iterator(cend());
  }
  const_reverse_iterator crbegin() const {
    return const_reverse_iterator(cend());
  }

  reverse_iterator rend() {
    return reverse_iterator(begin());
  }
  const_reverse_iterator rend() const {
    return const_reverse_iterator(cbegin());
  }
  const_reverse_iterator crend() const {
    return const_reverse_iterator(cbegin());
  }

  void insert(iterator it, const T& element) {
    ++size_;

    iterator iter = --end();
    while (iter != it) {
      *iter = *(iter - 1);
      --iter;
    }

    *it = element;
  }

  void erase(iterator it) {
    iterator iter = it + 1;

    while (iter != end()) {
      *(iter - 1) = *(iter);
      ++iter;
    }

    --size_;
  }

};