SlidingDeque

template <typename T, typename F>
struct SlidingDeque {
  F func;
  std::vector<T> head;
  std::vector<T> tail;
  std::vector<T> fhead;
  std::vector<T> ftail;

  SlidingDeque(const F& _func = F {}) : func(_func) {
    void(0);
  }

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

  [[nodiscard]] bool empty() const {
    return size() == 0;
  }

  [[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();
  }

  [[nodiscard]] T get() const {
    if (!fhead.empty() && !ftail.empty()) {
      return func(fhead.back(), ftail.back());
    } else if (!fhead.empty()) {
      return fhead.back();
    } else if (!ftail.empty()) {
      return ftail.back();
    } else {
      assert(false);
    }
  }

  void pushFront(const T& x) {
    const T nw = (head.empty() ? x : func(x, fhead.back()));
    head.push_back(x);
    fhead.push_back(std::move(nw));
  }

  void pushBack(const T& x) {
    const T nw = (tail.empty() ? x : func(ftail.back(), x));
    tail.push_back(x);
    ftail.push_back(std::move(nw));
  }

  void transportToHead() {
    head.insert(head.begin(), tail.rbegin() + int(tail.size()) / 2, tail.rend());
    tail.erase(tail.begin(), tail.end() - int(tail.size()) / 2);
    ftail = {};
    std::partial_sum(head.begin(), head.end(), std::back_inserter(fhead), [&](const T& a, const T& b) {
      return func(b, a);
    });
    std::partial_sum(tail.begin(), tail.end(), std::back_inserter(ftail), func);
  }

  void transportToTail() {
    tail.insert(tail.begin(), head.rbegin() + int(head.size()) / 2, head.rend());
    head.erase(head.begin(), head.end() - int(head.size()) / 2);
    fhead = {};
    std::partial_sum(head.begin(), head.end(), std::back_inserter(fhead), [&](const T& a, const T& b) {
      return func(b, a);
    });
    std::partial_sum(tail.begin(), tail.end(), std::back_inserter(ftail), func);
  }

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

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

  void clear() {
    head = {};
    tail = {};
    fhead = {};
    ftail = {};
  }
};