#pragma once
#include <iostream>

template<class T>
class Vector
{
public:
    Vector() : data_(nullptr), size_(0), allocated_(0) {}

    Vector(const Vector<T>& copy) : data_(new T[allocated_]), size_(copy.size_), allocated_(2 * copy.size_)
    {
        for (unsigned i = 0; i < size_; ++i)
        {
            data_[i] = copy.data_[i];
        }
    }

    Vector(const unsigned& count, const T& elem = {}) : data_(new T[allocated_]), size_(count), allocated_(2 * size_)
    {
        for (unsigned i = 0; i < size_; ++i)
        {
            data_[i] = elem;
        }
    }

    const unsigned& size() const
    {
        return size_;
    }

    const unsigned& allocated() const
    {
        return allocated_;
    }

    bool empty() const
    {
        return (!size_);
    }

    void resize(const unsigned& count, const T& elem = {})
    {
        if (count > allocated_)
        {
            allocated_ = 2 * count;
            T* newData = new T[allocated_];
            unsigned length = std::min(size_, count);
            for (unsigned i = 0; i < length; ++i)
            {
                newData[i] = data_[i];
            }
            delete[] data_;
            data_ = newData;
        }
        int length = count - size_;
        for (unsigned i = 0; i < length; ++i)
        {
            data_[size_ + i] = elem;
        }
        size_ = count;
    }

    void clear()
    {
        resize(0);
    }

    void reserve(const unsigned& allocated)
    {
        if (allocated > allocated_)
        {
            allocated_ = allocated;
            T* newData = new T[allocated_];
            for (unsigned i = 0; i < size_; ++i)
            {
                newData[i] = data_[i];
            }
            delete[] data_;
            data_ = newData;
        }
    }

    void shrink_to_fit()
    {
        if (allocated_ != size_)
        {
            allocated_ = size_;
            T* newData = new T[allocated_];
            for (unsigned i = 0; i < size_; ++i)
            {
                newData[i] = data_[i];
            }
            delete[] data_;
            data_ = newData;
        }
    }

    Vector<T> subsegment(const unsigned& l, const unsigned& r) const
    {
        assert(l < r && 0 <= l && r <= size_);
        Vector<T> res;
        res.size_ = r - l;
        res.allocated_ = res.size_;
        res.data_ = new T[res.allocated_];
        for (unsigned i = 0; i < res.size_; ++i)
        {
            res[i] = data_[i + l];
        }
        return res;
    }

    Vector<T> subsegment(const unsigned& l) const
    {
        return subsegment(l, size_);
    }

    int find(const T& elem, unsigned l, unsigned r)
    {
        assert(l < r && 0 <= l && r <= size_);
        for (unsigned i = l; i < r; ++i)
        {
            if (data_[i] == elem)
            {
                return i;
            }
        }
        return -1;
    }

    int rfind(const T& elem, unsigned l, unsigned r)
    {
        assert(l < r && 0 <= l && r <= size_);
        for (unsigned i = r - 1; i >= l; --i)
        {
            if (data_[i] == elem)
            {
                return i;
            }
        }
        return -1;
    }

    int find(const T& elem)
    {
        return find(elem, 0, size_);
    }

    int rfind(const T& elem)
    {
        return rfind(elem, 0, size_);
    }

    int findSubsegment(const Vector<T>& elem, unsigned l, unsigned r)
    {
        assert(l < r && 0 <= l && r <= size_);
        unsigned* pi = new unsigned[elem.size_];
        pi[0] = 0;
        unsigned j = 0;
        for (unsigned i = 1; i < elem.size_; ++i)
        {
            while (j > 0 && elem.data_[i] != elem.data_[j])
            {
                j = pi[j - 1];
            }
            pi[i] = (j += (elem.data_[i] == elem.data_[j]));
        }
        j = 0;
        for (unsigned i = 0; i < r; ++i)
        {
            while (j > 0 && elem.data_[j] != data_[i])
            {
                j = pi[j - 1];
            }
            j += (data_[i] == elem.data_[j]);
            if (l <= i - elem.size_ + 1 && i < r && j == elem.size_)
            {
                return i - elem.size_ + 1;
            }
        }
        delete[] pi;
        return -1;
    }

    int rfindSubsegment(const Vector<T>& elem, unsigned l, unsigned r)
    {
        int res = -1;
        assert(l < r && 0 <= l && r <= size_);
        unsigned* pi = new unsigned[elem.size_];
        pi[0] = 0;
        unsigned j = 0;
        for (unsigned i = 1; i < elem.size_; ++i)
        {
            while (j > 0 && elem.data_[i] != elem.data_[j])
            {
                j = pi[j - 1];
            }
            pi[i] = (j += (elem.data_[i] == elem.data_[j]));
        }
        j = 0;
        for (unsigned i = 0; i < r; ++i)
        {
            while (j > 0 && elem.data_[j] != data_[i])
            {
                j = pi[j - 1];
            }
            j += (data_[i] == elem.data_[j]);
            if (l <= i - elem.size_ + 1 && i < r && j == elem.size_)
            {
                res = i - elem.size_ + 1;
            }
        }
        delete[] pi;
        return res;
    }

    int findSubsegment(const Vector<T>& elem)
    {
        return findSubsegment(elem, 0, size_);
    }

    int rfindSubsegment(const Vector<T>& elem)
    {
        return rfindSubsegment(elem, 0, size_);
    }

    std::istream& getline(std::istream& in)
    {
        T elem;
        while (in.peek() != '\n')
        {
            in >> elem;
            *this += elem;
        }
        in.get();
        return in;
    }

    T& operator[](int id) const
    {
        id += (id < 0 ? size_ : 0);
        assert(0 <= id && id < (int)size_);
        return data_[id];
    }

    Vector<T>& operator=(const Vector<T>& right)
    {
        if (this == &right)
        {
            return *this;
        }
        delete[] data_;
        size_ = right.size_;
        allocated_ = 2 * size_;
        data_ = new T[allocated_];
        for (unsigned i = 0; i < size_; ++i)
        {
            data_[i] = right.data_[i];
        }
        return *this;
    }

    Vector<T>& operator=(const T& right)
    {
        delete[] data_;
        size_ = 1;
        allocated_ = 2;
        data_ = new T[allocated_];
        data_[0] = right;
        return *this;
    }

    Vector<T>& operator+=(const Vector<T>& right)
    {
        if (allocated_ - size_ < right.size_)
        {
            allocated_ = 2 * (size_ + right.size_);
            T* newData = new T[allocated_];
            for (unsigned i = 0; i < size_; ++i)
            {
                newData[i] = data_[i];
            }
            delete[] data_;
            data_ = newData;
        }
        for (unsigned i = size_; i < size_ + right.size_; ++i)
        {
            data_[i] = right.data_[i - size_];
        }
        size_ += right.size_;
        return *this;
    }

    Vector<T>& operator+=(const T& right)
    {
        if (allocated_ == size_)
        {
            allocated_ = 2 * (size_ + 1);
            T* newData = new T[allocated_];
            for (unsigned i = 0; i < size_; ++i)
            {
                newData[i] = data_[i];
            }
            delete[] data_;
            data_ = newData;
        }
        data_[size_] = right;
        size_++;
        return *this;
    }

    Vector<T> operator+(const Vector<T>& right) const
    {
        Vector<T> res;
        res.size_ = size_ + right.size_;
        res.allocated_ = 2 * res.size_;
        res.data_ = new T[res.allocated_];
        for (unsigned i = 0; i < size_; ++i)
        {
            res.data_[i] = data_[i];
        }
        for (unsigned i = 0; i < right.size_; ++i)
        {
            res.data_[i + size_] = right.data_[i];
        }
        return res;
    }

    Vector<T> operator+(const T& right) const
    {
        Vector<T> res;
        res.size_ = size_ + 1;
        res.allocated_ = 2 * res.size_;
        res.data_ = new T[res.allocated_];
        for (unsigned i = 0; i < size_; ++i)
        {
            res.data_[i] = data_[i];
        }
        res.data_[size_] = right;
        return res;
    }

    bool operator==(const Vector<T>& right) const
    {
        bool res = (size_ == right.size_);
        for (unsigned i = 0; res && i < right.size_; ++i)
        {
            res = (data_[i] == right.data_[i]);
        }
        return res;
    }

    bool operator==(const T& right) const
    {
        return (size_ == 1 && data_[0] == right);
    }

    bool operator!=(const Vector<T>& right) const
    {
        return !(*this == right);
    }

    bool operator!=(const T& right) const
    {
        return !(*this == right);
    }

    bool operator<(const Vector<T>& right) const
    {
        unsigned length = std::min(size_, right.size_);
        for (unsigned i = 0; i < length; ++i)
        {
            if (data_[i] < right.data_[i])
            {
                return true;
            }
        }
        return (size_ < right.size_);
    }

    bool operator<(const T& right) const
    {
        return (!size_ || data_[0] < right);
    }

    bool operator<=(const Vector<T>& right) const
    {
        return (*this < right || *this == right);
    }

    bool operator<=(const T& right) const
    {
        return (*this < right || *this == right);
    }

    bool operator>(const Vector<T>& right) const
    {
        unsigned length = std::min(size_, right.size_);
        for (unsigned i = 0; i < length; ++i)
        {
            if (data_[i] > right.data_[i])
            {
                return true;
            }
        }
        return (size_ > right.size_);
    }

    bool operator>(const T& right) const
    {
        return (data_[0] > right || data_[0] == right && size_ > 1);
    }

    bool operator>=(const Vector<T>& right) const
    {
        return (*this > right || *this == right);
    }

    bool operator>=(const T& right) const
    {
        return (*this > right || *this == right);
    }

    friend std::istream& operator>>(std::istream& in, Vector<T>& v)
    {
        for (unsigned i = 0; i < v.size_; ++i)
        {
            in >> v[i];
        }
        return in;
    }

    friend std::ostream& operator<<(std::ostream& out, const Vector<T>& v)
    {
        for (unsigned i = 0; i < v.size_; ++i)
        {
            out << v.data_[i] << ' ';
        }
        return out;
    }

    class reverse_iterator;

    class iterator
    {
    public:

        iterator(T* ptr, T* left, T* right) : current_(ptr), left_(left), right_(right) {}

        iterator(const iterator& copy) : current_(copy.current_), left_(copy.left_), right_(copy.right_) {}

        reverse_iterator getReversible() const
        {
            return reverse_iterator(current_, left_, right_);
        }

        iterator& operator=(const iterator& right)
        {
            current_ = right.current_;
            return *this;
        }

        T operator[](int id)
        {
            return *(current_ + id);
        }

        T* operator->() const
        {
            return current_;
        }

        iterator operator+(int right) const
        {
            return iterator(current_ + right, left_, right_);
        }

        iterator operator-(int right) const
        {
            return iterator(current_ - right, left_, right_);
        }

        iterator operator++(int)
        {
            iterator res(current_, left_, right_);
            current_++;
            return res;
        }

        iterator operator--(int)
        {
            iterator res(current_, left_, right_);
            current_--;
            return res;
        }

        iterator& operator++()
        {
            ++current_;
            return *this;
        }

        iterator& operator--()
        {
            --current_;
            return *this;
        }

        iterator& operator+=(int right)
        {
            current_ += right;
            return *this;
        }

        iterator& operator-=(int right)
        {
            current_ -= right;
            return *this;
        }

        T& operator*()
        {
            assert(left_ <= current_ && current_ < right_);
            return *current_;
        }

        const T& operator*() const
        {
            assert(left_ <= current_ && current_ < right_);
            return *current_;
        }

        bool operator==(const iterator& right)
        {
            return current_ == right.current_;
        }

        bool operator!=(const iterator& right)
        {
            return current_ != right.current_;
        }

        bool operator<(const iterator& right)
        {
            return current_ < right.current_;
        }

        bool operator>(const iterator& right)
        {
            return current_ > right.current_;
        }

        bool operator<=(const iterator& right)
        {
            return current_ <= right.current_;
        }

        bool operator>=(const iterator& right)
        {
            return current_ >= right.current_;
        }

    private:
        T* left_;
        T* current_;
        T* right_;
    };

    class reverse_iterator
    {
    public:

        reverse_iterator(T* ptr, T* left, T* right) : current_(ptr), left_(left), right_(right) {}

        reverse_iterator(const reverse_iterator& copy) : current_(copy.current_), left_(copy.left_), right_(copy.right_) {}

        iterator getStraight() const
        {
            return iterator(current_, left_, right_);
        }

        reverse_iterator& operator=(const reverse_iterator& right)
        {
            current_ = right.current_;
            return *this;
        }

        T operator[](int id)
        {
            return *(current_ - id);
        }

        T* operator->() const
        {
            return current_;
        }

        reverse_iterator operator+(int right) const
        {
            return reverse_iterator(current_ - right, left_, right_);
        }

        reverse_iterator operator-(int right) const
        {
            return reverse_iterator(current_ + right, left_, right_);
        }

        reverse_iterator operator++(int)
        {
            reverse_iterator res(current_, left_, right_);
            current_--;
            return res;
        }

        reverse_iterator operator--(int)
        {
            reverse_iterator res(current_, left_, right_);
            current_++;
            return res;
        }

        reverse_iterator& operator++()
        {
            --current_;
            return *this;
        }

        reverse_iterator& operator--()
        {
            ++current_;
            return *this;
        }

        reverse_iterator& operator+=(int right)
        {
            current_ += right;
            return *this;
        }

        reverse_iterator& operator-=(int right)
        {
            current_ -= right;
            return *this;
        }

        T& operator*()
        {
            assert(left_ <= current_ && current_ < right_);
            return *current_;
        }

        const T& operator*() const
        {
            assert(left_ <= current_ && current_ < right_);
            return *current_;
        }

        bool operator==(const reverse_iterator& right)
        {
            return current_ == right.current_;
        }

        bool operator!=(const reverse_iterator& right)
        {
            return current_ != right.current_;
        }

        bool operator<(const reverse_iterator& right)
        {
            return current_ > right.current_;
        }

        bool operator>(const reverse_iterator& right)
        {
            return current_ < right.current_;
        }

        bool operator<=(const reverse_iterator& right)
        {
            return current_ >= right.current_;
        }

        bool operator>=(const reverse_iterator& right)
        {
            return current_ <= right.current_;
        }

    private:
        T* left_;
        T* current_;
        T* right_;
    };

    iterator begin() const
    {
        return iterator(data_, data_, data_ + size_);
    }

    iterator end() const
    {
        return iterator(data_ + size_, data_, data_ + size_);
    }

    reverse_iterator rbegin() const
    {
        return reverse_iterator(data_ + size_ - 1, data_, data_ + size_);
    }

    reverse_iterator rend() const
    {
        return reverse_iterator(data_ - 1, data_, data_ + size_);
    }

    ~Vector()
    {
        delete[] data_;
    }

private:
    unsigned size_;
    unsigned allocated_;
    T* data_;
};