#include <iostream>
#include <vector>

template <size_t N>
class StackStorage {
 private:
  std::vector<char*> memory_;
 public:
  StackStorage() = default;
  ~StackStorage() = default;

  void* allocate() {
    void* ptr = memory_.back();
    memory_.pop_back();
    return ptr;
  }

  void deallocate(void* p, size_t n) {} // ignoring deallocate

  static StackStorage<N>& get_instance() {
    static StackStorage<N> alloc;
    return alloc;
  }
};

template <typename T>
class StackAllocator {
 public:
  StackAllocator() = default;

  template<typename U>
  StackAllocator(const StackAllocator<U>& other) {}

  ~StackAllocator() = default;


  using value_type = T;
  using pointer = T*;
  using const_pointer = const T*;
  using reference = T&;
  using const_refernce = const T&;
  using size_type = std::size_t;

  T* allocate(size_t n) {
    const size_t alloc_size = n * sizeof(T);
    if (alloc_size <= 4) {
      return static_cast<T*>(StackStorage<4>::get_instance().allocate());
    }
    if (alloc_size <= 8) {
      return static_cast<T*>(StackStorage<8>::get_instance().allocate());
    }
    if (alloc_size <= 16) {
      return static_cast<T*>(StackStorage<16>::get_instance().allocate());
    }
    return static_cast<T*>(StackStorage<32>::get_instance().allocate());
  }

  void deallocate(T* p, size_t n) {
    const size_t alloc_size = n * sizeof(T);
    if (alloc_size <= 4) {
      StackStorage<4>::get_instance().deallocate(p, 4);
      return;
    }
    if (alloc_size <= 8) {
      StackStorage<8>::get_instance().deallocate(p, 8);
      return;
    }
    if (alloc_size <= 16) {
      StackStorage<16>::get_instance().deallocate(p, 16);
      return;
    }
    StackStorage<32>::get_instance().deallocate(p, 32);
  }

  template <typename U>
  struct rebind {
    typedef StackAllocator<U> other;
  };

  template<typename U>
  bool operator==(const StackAllocator<U>& other) const {
    return true;
  }

  template<typename U>
  bool operator!=(const StackAllocator<U>& other) const {
    return false;
  }
};

// List
template<typename T, typename Allocator = std::allocator<T>>
class List {
 private:
  struct Node {
    T node_value_;
    Node* next;
    Node* prev;

    Node(): next(nullptr), prev(nullptr) {}
    ~Node() = default;
    Node(const T& value): node_value_(value) {}
  };

  size_t size_;
  Node* head_;


  Allocator alloc;
  typename Allocator::template rebind<Node>::other allocator;

  void put_after(Node* p, Node* value) const {
    value->prev = p;
    value->next = p->next;
    p->next = value;
    p->next->prev = value;
  }

 public:
  // not implamented
  template<bool is_const>
  class Iterator {
   public:
    std::conditional_t<is_const, const Node*, Node*> ptr_;

    Iterator(): ptr_(nullptr) {}
    Iterator(std::conditional_t<is_const, const Node*, Node*> ptr): ptr_(ptr) {}
    ~Iterator() = default;

    Iterator& operator++() {
      ptr_ = ptr_->next;
      return *this;
    }

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

    Iterator& operator--() {
      ptr_ = ptr_->prev;
      return *this;
    }

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

    bool operator==(const Iterator& other) const {
      return ptr_ == other.ptr_;
    }

    bool operator!=(const Iterator& other) const {
      return ptr_ != other.ptr_;
    }

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

    std::conditional_t<is_const, const T&, T&> operator->() const {
      return &(ptr_->val_);
    }
  };

  using iterator = Iterator<false>;
  using const_iterator = Iterator<true>;
  using reverse_iterator = std::reverse_iterator<iterator>;
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
  using alloc_traits = std::allocator_traits<typename Allocator::template rebind<Node>::other>;

  // 1
  List();
  explicit List(size_t count);
  explicit List(size_t count, const T& value);
  explicit List(const Allocator& alloc = Allocator());
  explicit List(int count, const Allocator& alloc = Allocator());
  explicit List(size_t count, const T& value, const Allocator& alloc = Allocator());

  // 2
  List(const List& other) {} // not

  List& operator=(const List& other) {} // not

  ~List() {} // not

  // 3
  [[nodiscard]] size_t size() const {
    return size_;
  }

  Allocator get_allocator() const {
    return alloc;
  }

  // 4
  void push_back(const T& value) {
    insert(end(), value);
  }
  void push_front(const T& value) {
    insert(begin(), value);
  }
  void pop_back() {
    erase(--end());
  }
  void pop_front() {
    erase(begin());
  }

  // 5
  iterator begin() {
    return iterator(head_->next);
  }
  const_iterator begin() const {
    return const_iterator(head_->next);
  }
  const_iterator cbegin() const {
    return const_iterator(head_->next);
  }

  iterator end() {
    return iterator(head_);
  }
  const_iterator end() const {
    return const_iterator(head_);
  }
  const_iterator cend() const {
    return const_iterator(head_);
  }

  reverse_iterator rbegin() {
    return reverse_iterator(head_);
  }

  const_reverse_iterator rbegin() const {
    return const_reverse_iterator(head_);
  }
  const_reverse_iterator crbegin() const {
    return const_reverse_iterator(head_);
  }

  reverse_iterator rend() {
    return reverse_iterator(head_->next);
  }
  const_reverse_iterator rend() const {
    return const_reverse_iterator(head_->next);
  }
  const_reverse_iterator crend() const {
    return const_reverse_iterator(head_->next);
  }

  // 6
  iterator insert(const_iterator pos, const T& value) {}
  iterator erase(const_iterator pos) {}
};

int main() {
  return 0;
}