Deque

template <typename T>
struct Deque {
  std::vector<T> head;
  std::vector<T> tail;

  [[nodiscard]] int size() const {
    return int(head.size()) + int(tail.size());
  }

  [[nodiscard]] bool empty() const {
    return size() == 0;
  }
  
  [[nodiscard]] T& operator[](int index) {
    assert(0 <= index && index < size());
    return (index < int(head.size()) ? head[int(head.size()) - 1 - index] : tail[index - int(head.size())]);
  }

  [[nodiscard]] const T& operator[](int index) const {
    assert(0 <= index && index < size());
    return (index < int(head.size()) ? head[int(head.size()) - 1 - index] : tail[index - int(head.size())]);
  }

  [[nodiscard]] const T& front() const {
    assert(!empty());
    return head.empty() ? tail.front() : head.back();
  }

  [[nodiscard]] const T& back() const {
    assert(!empty());
    return tail.empty() ? head.front() : tail.back();
  }

  void pushFront(const T& x) {
    head.push_back(x);
  }

  void pushBack(const T& x) {
    tail.push_back(x);
  }

  void transportToHead() {
    head.insert(head.begin(), tail.rbegin() + int(tail.size()) / 2, tail.rend());
    tail.erase(tail.begin(), tail.end() - int(tail.size()) / 2);
  }

  void transportToTail() {
    tail.insert(tail.begin(), head.rbegin() + int(head.size()) / 2, head.rend());
    head.erase(head.begin(), head.end() - int(head.size()) / 2);
  }

  void popFront() {
    if (head.empty()) {
      transportToHead();
    }
    head.pop_back();
  }

  void popBack() {
    assert(!empty());
    if (!tail.empty()) {
      transportToTail();
    }
    tail.pop_back();
  }
};