#include <cstddef>
#include <new>
#include <utility>
#include <memory>
#include <iostream>

template <typename T>
struct RawMemory {
  T* buf = nullptr;
  size_t cp = 0;

  static T* Allocate(size_t n) {
    return static_cast<T*>(operator new(n * sizeof(T)));
  }

  static void Deallocate(T* buf) {
    operator delete(buf);
  }

  RawMemory() = default;

  RawMemory(size_t n) {
    buf = Allocate(n);
    cp = n;
  }

  RawMemory(const RawMemory&) = delete;

  RawMemory(RawMemory&& other) {
    Swap(other);
  }

  ~RawMemory() {
    Deallocate(buf);
  }

  T* operator+(size_t i) {
    return buf+i;
  }

  const T* operator+(size_t i) const {
    return buf+i;
  }

  T& operator[](size_t i) {
    return buf[i];
  }

  const T& operator[](size_t i) const {
    return buf[i];
  }

  RawMemory& operator=(const RawMemory&) = delete;

  RawMemory& operator=(RawMemory&& other) {
    Swap(other);
    return *this;
  }

  void Swap(RawMemory& other) {
    std::swap(buf, other.buf);
    std::swap(cp, other.cp);
  }
};

template <typename T>
class Vector {
public:

  Vector() = default;

  Vector(size_t n) : data(n) {
    std::uninitialized_value_construct_n(data.buf, n);
    sz = n;
  }

  Vector(const Vector& other) : data(other.sz) {
    std::uninitialized_copy_n(other.data.buf, other.sz, data.buf);
    sz = other.sz;
  }

  Vector(Vector&& other) {
    Swap(other);
  }

  ~Vector() {
    std::destroy_n(data.buf, sz);
  }

  void Swap(Vector& other) {
    data.Swap(other.data);
    std::swap(sz, other.sz);
  }

  Vector& operator = (const Vector& other) {
    if (other.sz > data.cp) {
      Vector tmp(other);
      Swap(tmp);
      return *this;
    }
    for (size_t i = 0; i < sz && i < other.sz; i++) {
      data[i] = other.data[i];
    }
    if (sz < other.sz) {
      std::uninitialized_copy_n(other.data.buf + sz, other.sz - sz, data.buf + sz);
    } else {
      std::destroy_n(data.buf + other.sz, sz - other.sz);
    }
    sz = other.sz;
    return *this;
  }

  Vector& operator = (Vector&& other) noexcept {
    Swap(other);
    return *this;
  }

  void Reserve(size_t n) {
    if (n > data.cp) {
      RawMemory<T> data2(n);
      std::uninitialized_move_n(data.buf, sz, data2.buf);
      std::destroy_n(data.buf, sz);
      data.Swap(data2);
    }
  }

  void Resize(size_t n) {
    Reserve(n);
    if (n > sz) {
      std::uninitialized_value_construct_n(data.buf + sz, n - sz);
    } else {
      std::destroy_n(data.buf + n, sz - n);
    }
    sz = n;
  }

  void PushBack(const T& elem) {
    if (sz == data.cp) {
      Reserve(sz == 0 ? 1 : sz * 2);
    }
    new (data+sz) T(elem);
    ++sz;
  }

  void PushBack(T&& elem) {
    if (sz == data.cp) {
      Reserve(sz == 0 ? 1 : sz * 2);
    }
    new (data+sz) T(std::move(elem));
    ++sz;
  }

  template <typename ... Args>
  T& EmplaceBack(Args&&... args) {
    if (data.cp == sz) {
      Reserve(sz == 0 ? 1 : sz * 2);
    }
    auto elem = new (data.buf + sz) T(std::forward<Args>(args)...);
    ++sz;
    return *elem;
  }

  void PopBack() {
    data[sz-1].~T();
    --sz;
  }

  size_t Size() const noexcept {
    return sz;
  }

  size_t Capacity() const noexcept {
    return data.cp;
  }

  const T& operator[](size_t i) const {
    return data[i];
  }

  T& operator[](size_t i) {
    return data[i];
  }

  using iterator = T*;
  using const_iterator = const T*;

  iterator begin() noexcept {
    return data.buf;
  }
  iterator end() noexcept {
    return data.buf + sz;
  }

  const_iterator begin() const noexcept {
    return data.buf;
  }
  const_iterator end() const noexcept {
    return data.buf + sz;
  }

  // Тут должна быть такая же реализация, как и для константных версий begin/end
  const_iterator cbegin() const noexcept {
    return data.buf;
  }
  const_iterator cend() const noexcept {
    return data.buf + sz;
  }

  void ShiftFrom(size_t idx) {
    new (data+sz) T(std::move(data[sz-1]));
    for (size_t i = sz-1; i > idx; i--) {
      data[i] = std::move(data[i-1]);
    }
  }

  // Вставляет элемент перед pos
  // Возвращает итератор на вставленный элемент
  iterator Insert(const_iterator pos, const T& elem) {
    size_t idx = pos - data.buf;
    if (data.cp == sz) {
      Reserve(sz == 0 ? 1 : sz * 2);
    }
    if (idx == sz) {
      new (data.buf+sz) T(elem);
    } else {
      ShiftFrom(idx);
      data[idx] = elem;
    }
    ++sz;
    return data.buf + idx;
  }
  iterator Insert(const_iterator pos, T&& elem) {
    size_t idx = pos - data.buf;
    if (data.cp == sz) {
      Reserve(sz == 0 ? 1 : sz * 2);
    }
    if (idx == sz) {
      new (data+sz) T(std::move(elem));
    } else {
      ShiftFrom(idx);
      data[idx] = std::move(elem);
    }
    ++sz;
    return data.buf +idx;
  }

  // Конструирует элемент по заданным аргументам конструктора перед pos
  // Возвращает итератор на вставленный элемент
  template <typename ... Args>
  iterator Emplace(const_iterator it, Args&&... args) {
    size_t idx = it - data.buf;
    if (data.cp == sz) {
      Reserve(sz == 0 ? 1 : sz * 2);
    }
    if (idx == sz) {
      new (data.buf + sz) T(std::forward<Args>(args)...);
    } else {
      ShiftFrom(idx);
      data[idx] = T(std::forward<Args>(args)...);
    }
    ++sz;
    return data.buf + idx;
  }

  // Удаляет элемент на позиции pos
  // Возвращает итератор на элемент, следующий за удалённым
  iterator Erase(const_iterator it) {
    size_t idx = it - data.buf;
    data[idx].~T();
    for (size_t i = idx; i < sz; i++) {
      data[i] = std::move(data[i+1]);
    }
    data[sz-1].~T();
    --sz;
    return data.buf + idx;
  }

private:
  RawMemory<T> data;
  size_t sz = 0;
};