#include <memory>
#include <vector>
#include <iterator>

template<size_t chunkSize>
class FixedAllocator {
 private:
  static const int count_chunks = 16;
  static inline std::vector<void*> free;
 public:
  [[nodiscard]] static void* allocate() {
    if (free.empty()) {
      char* tmp = new char[chunkSize * count_chunks];
      for (int i = 0; i < count_chunks; ++i) free.push_back(reinterpret_cast<void*>(tmp + i * chunkSize));
    }
    void* tmp = free.back();
    free.pop_back();
    return tmp;
  }

  static void deallocate(void* p) {
    free.push_back(p);
  }
};

template<typename T>
class FastAllocator {
 public:
  using value_type = T;
  FastAllocator() = default;

  template<typename U>
  FastAllocator(const FastAllocator<U>&) {}

  template<typename U>
  FastAllocator& operator=(const FastAllocator<U>&) const { return *this; }

  [[nodiscard]] T* allocate(size_t n) {
    if (n * sizeof(T) > kSizeBigBlock)
      return reinterpret_cast<T*>(new char[n * sizeof(T)]);
    else {
      return reinterpret_cast<T*>(allocate_template_for<sizeof(T), kSizeBigBlock>(sizeof(T) * n));
    }
  }

  void deallocate(T* p, size_t n) {
    if (n * sizeof(T) > 48)
      delete[] reinterpret_cast<char*>(p);
    else
      deallocate_template_for<sizeof(T), kSizeBigBlock>(p, n * sizeof(T));
  }
 private:
  static const size_t kSizeBigBlock = 48;

  template<size_t x = 1, size_t end = kSizeBigBlock>
  [[nodiscard]] void* allocate_template_for(size_t n) {
    if (x == n) {
      return FixedAllocator<x>::allocate();
    } else {
      if constexpr (x < end)  {
        return allocate_template_for<x + 1, end>(n);
      }
    }
    return nullptr;
  }

  template<size_t x = 1, size_t end = kSizeBigBlock>
  void deallocate_template_for(void* ptr, size_t n) {
    if (x == n) {
      FixedAllocator<x>::deallocate(ptr);
    } else {
      if constexpr (x < end)  {
        deallocate_template_for<x + 1, end>(ptr, n);
      }
    }
  }

};

template<class T, class U>
bool operator==(const FastAllocator<T>& a, const FastAllocator<U>& b) {
  return &a == &b;
}

template<class T, class U>
bool operator!=(const FastAllocator<T>& a, const FastAllocator<U>& b) {
  return !(a == b);
}

template<typename T, typename Allocator=std::allocator<T>>
class List {
 private:
  class Node;

  template<bool is_const>
  class base_iterator;
 public:
  using iterator = base_iterator<false>;
  using const_iterator = base_iterator<true>;
  using reverse_iterator = std::reverse_iterator<iterator>;
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;

  explicit List(const Allocator& alloc = Allocator()) : alloc_(alloc) {
    AllocateEndNode();
  }

  List(size_t count, const T& value, const Allocator& alloc = Allocator()) : alloc_(alloc) {
    AllocateEndNode();

    for (size_t i = 0; i < count; ++i) {
      Node* tmp = alloc_.allocate(1);
      alloc_traits_::construct(alloc_, tmp, value);
      Link(end_->l, tmp);
    }
    size_ = count;
  }

  List(size_t count, const Allocator& alloc = Allocator()) : alloc_(alloc) {
    AllocateEndNode();

    for (size_t i = 0; i < count; ++i) {
      Node* tmp = alloc_.allocate(1);
      alloc_traits_::construct(alloc_, tmp);
      Link(end_->l, tmp);
    }
    size_ = count;
  }

  List(const List& another) {
    alloc_ = alloc_traits_::select_on_container_copy_construction(another.alloc_);
    AllocateEndNode();
    for (const T& i: another) {
      Node* tmp = alloc_.allocate(1);
      alloc_traits_::construct(alloc_, tmp, i);
      Link(end_->l, tmp);
    }
    size_ = another.size();
  }

  List& operator=(const List& another) {
    if (this == &another) return *this;
    if (alloc_traits_::propagate_on_container_copy_assignment::value && alloc_ != another.alloc_) {
      alloc_ = another.alloc_;
    }

    auto it1 = begin();
    auto it2 = another.begin();
    for (size_t i = 0; i < std::min(another.size(), size()); ++i) {
      *it1 = *it2;
      ++it1;
      ++it2;
    }
    if (another.size() > size()) {
      while (size() != another.size()) {
        push_back(*it2);
        ++it2;
      }
    } else {
      while (size() != another.size()) {
        pop_back();
      }
    }

    return *this;
  }

  ~List() {
    while (end_ != end_->r) {
      erase(iterator(end_->r));
    }
    alloc_.deallocate(end_, 1);
  }

  Allocator get_allocator() {
    return alloc_;
  }

  void push_back(const T& value) {
    insert(end(), value);
  }

  void push_front(const T& value) {
    insert(begin(), value);
  }

  void pop_back() {
    erase(std::prev(end()));
  }

  void pop_front() {
    erase(begin());
  }

  size_t size() const { return size_; }

  iterator begin() { return iterator(end_->r); }
  iterator end() { return iterator(end_); }

  const_iterator begin() const { return const_iterator(end_->r); }
  const_iterator end() const { return const_iterator(end_); }

  const_iterator cbegin() const { return const_iterator(end_->r); }
  const_iterator cend() const { return const_iterator(end_); }

  reverse_iterator rbegin() { return reverse_iterator(end()); }
  reverse_iterator rend() { return reverse_iterator(begin()); }

  const_reverse_iterator rbegin() const { return const_reverse_iterator(cend()); }
  const_reverse_iterator rend() const { return const_reverse_iterator(cbegin()); }

  const_reverse_iterator crbegin() const { return const_reverse_iterator(cend()); }
  const_reverse_iterator crend() const { return const_reverse_iterator(cbegin()); }

  void insert(const_iterator it, const T& value) {
    Node* tmp = alloc_.allocate(1);
    std::allocator_traits<decltype(alloc_)>::construct(alloc_, tmp, value);
    Link(const_cast<Node*>(std::prev(it).it), tmp);
    ++size_;
  }

  void erase(const_iterator it) {
    Node* tmp = const_cast<Node*>(it.it);
    tmp->l->r = tmp->r;
    tmp->r->l = tmp->l;
    std::allocator_traits<decltype(alloc_)>::destroy(alloc_, tmp);
    alloc_.deallocate(tmp, 1);
    --size_;
  }

 private:

  void AllocateEndNode() {
    end_ = alloc_.allocate(1);
    end_->l = end_;
    end_->r = end_;
  }

  void Link(Node* l, Node* x) {
    Node* r = l->r;
    x->l = l;
    x->r = r;
    l->r = x;
    r->l = x;
  }

  template<bool is_const>
  class base_iterator {
    friend List;
    std::conditional_t<is_const, const Node*, Node*> it;
    using U = std::conditional_t<is_const, const T, T>;
   public:

    using iterator_category = std::bidirectional_iterator_tag;
    using value_type = U;
    using pointer = U*;
    using reference = U&;
    using difference_type = int;

    base_iterator() : it(nullptr) {}
    base_iterator(Node* v) { it = v; }

    base_iterator(const base_iterator&) = default;
    operator base_iterator<true>() { return base_iterator<true>(it); }

    U& operator*() const { return it->value; }
    U* operator->() const { return &it->value; }
    base_iterator& operator++()& {
      it = it->r;
      return *this;
    }
    base_iterator operator++(int)& {
      base_iterator tmp = *this;
      it = it->r;
      return tmp;
    }
    base_iterator& operator--()& {
      it = it->l;
      return *this;
    }
    base_iterator operator--(int)& {
      base_iterator tmp = *this;
      it = it->l;
      return tmp;
    }

    friend bool operator==(base_iterator first, base_iterator second) { return first.it == second.it; }

    friend bool operator!=(base_iterator first, base_iterator second) { return !(first == second); }

    base_iterator& operator=(const base_iterator<false>& another) {
      it = another.it;
      return *this;
    }
  };

  struct Node {
    Node* l = nullptr;
    Node* r = nullptr;
    T value;
    Node() = default;
    Node(const T& value) : value(value) {}
    Node& operator=(const Node& another) { value = another.value; }
  };
  typename std::allocator_traits<Allocator>::template rebind_alloc<Node> alloc_;
  using alloc_traits_ = std::allocator_traits<decltype(alloc_)>;
  Node* end_ = nullptr;
  size_t size_ = 0;
};