#include <iostream>
#include <iterator>
#include <vector>

template<typename T>
class Deque {
 private:
  std::vector<T*> array_;
  size_t size_ = 0;
  size_t array_size_ = 0;
  size_t head_block_ind_ = 0;
  size_t head_buf_ind_ = 0;

  const static size_t block_size = 8;

  void resize(size_t new_array_size) {
    if (new_array_size < array_size_) {
      return;
    }
    std::vector<T*> temp_array;

    size_t new_head_buf_ind = (new_array_size - array_size_) / 2;
    for (size_t i = 0; i < new_head_buf_ind; ++i) {
      temp_array.push_back(reinterpret_cast<T*>(new char[block_size * sizeof(T)]));
    }
    for (size_t i = 0; i < array_size_; ++i) {
      temp_array.push_back(array_[i]);
    }
    for (size_t i = new_head_buf_ind + array_size_; i < new_array_size; ++i) {
      temp_array.push_back(reinterpret_cast<T*>(new char[block_size * sizeof(T)]));
    }

    array_ = temp_array;
    array_size_ = new_array_size;
    head_block_ind_ = (head_block_ind_ + new_head_buf_ind * block_size) % block_size;
    head_buf_ind_ = new_head_buf_ind;
  }
 public:
  Deque() {
    resize(1);
  }

  explicit Deque(size_t size) {
    resize(size / block_size + 1);
    for (size_t i = 0; i < size; ++i) {
      push_back(T());
    }
  }

  Deque(size_t size, const T& value) {
    resize(1);
    for (size_t i = 0; i < size; ++i) {
      push_back(value);
    }
  }
  Deque(const Deque& other) {
    try {
      resize(1);
      for (size_t i = 0; i < other.size_; ++i) {
        push_back(other[i]);
      }
    } catch (...) {
      throw;
    }
  }

  Deque& operator=(const Deque& other) {
    array_ = other.array_;
    size_ = other.size_;
    array_size_ = other.array_size_;
    head_block_ind_ = other.head_block_ind_;
    head_buf_ind_ = other.head_buf_ind_;

    return *this;
  }

  size_t size()  const {
    return size_;
  }

  T& operator[](size_t index) {
    return array_[head_buf_ind_ + (head_block_ind_ + index) / block_size][(head_block_ind_ + index) % block_size];
  }
  const T& operator[](size_t index) const {
    return array_[head_buf_ind_ + (head_block_ind_ + index) / block_size][(head_block_ind_ + index) % block_size];
  }
  T& at(size_t index) {
    if (index >= size_) {
      throw std::out_of_range("AtError: Index is out of range!");
    }
    return array_[head_buf_ind_ + (head_block_ind_ + index) / block_size][(head_block_ind_ + index) % block_size];
  }
  const T& at(size_t index) const {
    if (index >= size_) {
      throw std::out_of_range("AtError: Index is out of range!");
    }
    return array_[head_buf_ind_ + (head_block_ind_ + index) / block_size][(head_block_ind_ + index) % block_size];
  }

  void push_back(T value) {
    if (head_buf_ind_ + (head_block_ind_ + size_) / block_size == array_size_) {
      resize(3 * array_size_);
    }
    try {
      new(array_[head_buf_ind_ + (head_block_ind_ + size_) / block_size] + (head_block_ind_ + size_) % block_size) T(value);
      ++size_;
    } catch (...) {
      throw;
    }
  }

  void push_front(T value) {
    if (head_block_ind_ == 0 && head_buf_ind_ == 0) {
      resize(3 * array_size_);
    }
    try {
      new(array_[head_block_ind_ == 0 ? head_buf_ind_ - 1 : head_buf_ind_] + (head_block_ind_ - 1 + block_size) % block_size) T(value);
      ++size_;
      if (!head_block_ind_) {
        --head_buf_ind_;
      }
      head_block_ind_ = (head_block_ind_ - 1 + block_size) % block_size;
    } catch (...) {
      throw;
    }
  }

  void pop_back() {
    size_t tail_buf_ind = head_buf_ind_ + (head_block_ind_ + size_) / block_size;
    size_t tail_block_ind = (head_block_ind_ + size_) % block_size;
    (array_[tail_buf_ind] + tail_block_ind)->~T();
    --size_;
  }

  void pop_front() {
    (array_[head_buf_ind_] + head_block_ind_)->~T();
    head_buf_ind_ += (head_block_ind_ + 1) / block_size;
    head_block_ind_ = (head_block_ind_ + 1) % block_size;
    --size_;
  }

  template<bool is_const>
  class Iterator {
   private:
    friend class Deque;

    size_t cur_buff_index;
    size_t cur_block_index;
    std::conditional_t<is_const, const T*, T*> ptr;

    const std::vector<T *> *vector_ptr;
   public:
    Iterator(std::conditional_t<is_const, const Deque&, Deque&> deque_, size_t index) {
      cur_block_index = (deque_.head_block_ind_ + index) % block_size;
      cur_buff_index = deque_.head_buf_ind_ + (deque_.head_block_ind_ + index) / block_size;
      ptr = deque_.array_[cur_buff_index] + cur_block_index;
      vector_ptr = &deque_.array_;
    }

    Iterator& operator++() {
      ++cur_block_index;
      if (cur_block_index == block_size) {
        ++cur_buff_index;
        ptr = (*vector_ptr)[cur_buff_index];
        cur_block_index = 0;
      } else {
        ++ptr;
      }

      return *this;
    }

    Iterator operator++(int) {
      Iterator copy = *this;
      ++*this;
      return copy;
    }

    Iterator& operator--() {
      if (cur_block_index == 0u) {
        --cur_buff_index;
        ptr = (*vector_ptr)[cur_buff_index] + block_size - 1;
        cur_block_index = block_size - 1;
      } else {
        --cur_block_index;
        --ptr;
      }

      return *this;
    }

    Iterator operator--(int) {
      Iterator copy = *this;
      --*this;
      return copy;
    }

    Iterator& operator+=(int n) {
      size_t all_index = block_size * cur_buff_index + cur_block_index + n;

      cur_buff_index = all_index / block_size;
      cur_block_index = all_index % block_size;
      ptr = (*vector_ptr)[cur_buff_index] + cur_block_index;
      return *this;
    }

    Iterator operator+(int x) {
      Iterator result = *this;
      result += x;
      return result;
    }

    Iterator& operator-=(int n) {
      size_t all_index = block_size * cur_buff_index + cur_block_index - n;

      cur_buff_index = all_index / block_size;
      cur_block_index = all_index % block_size;
      ptr = (*vector_ptr)[cur_buff_index] + cur_block_index;
      return *this;
    }

    Iterator operator-(int x) {
      Iterator result = *this;
      result -= x;
      return result;
    }

    int operator-(const Iterator &other) const {
      size_t all_index = cur_buff_index * block_size + cur_block_index;
      size_t other_all_index = other.cur_buff_index * block_size + other.cur_block_index;
      return all_index - other_all_index;
    }

    bool operator==(const Iterator& other) const {
      return ptr == other.ptr;
    }
    bool operator!=(const Iterator& other) const {
      return ptr != other.ptr;
    }
    bool operator<(const Iterator& other) const {
      return cur_buff_index < other.cur_buff_index || (cur_buff_index == other.cur_buff_index && cur_block_index < other.cur_block_index);
    }
    bool operator>(const Iterator& other) const {
      return other < *this;
    }
    bool operator<=(const Iterator& other) const {
      return *this == other || *this < other;
    }
    bool operator>=(const Iterator& other) const {
      return *this == other || *this > other;
    }

    std::conditional_t<is_const, const T &, T &> operator*() const {
      return *ptr;
    }

    std::conditional_t<is_const, const T *, T *> operator->() const {
      return ptr;
    }
  };

  using const_iterator = Iterator<true>;
  using iterator = Iterator<false>;
  using reverse_iterator = std::reverse_iterator<iterator>;
  using const_reverse_iterator = std::reverse_iterator<const_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 std::make_reverse_iterator(end());
  }
  const_reverse_iterator crbegin() const {
    return std::make_reverse_iterator(cend());
  }

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

  void insert(iterator it, const T &value) {
    push_back(value);
    iterator it_ = end();
    --it_;
    iterator prev_it = it_;
    --prev_it;
    for (; it_ > it; --it_, --prev_it) {
      std::swap(*it_, *(prev_it));
    }
  }

  void erase(iterator it) {
    iterator it_ = it;
    iterator next_it = it_;
    ++next_it;
    for (; it_ < end(); ++it_, ++next_it) {
      std::swap(*it_, *(next_it));
    }
    pop_back();
  }
};