// deque standard header

#if     _MSC_VER > 1000 /*IFSTRIP=IGN*/
#pragma once
#endif

#ifndef _DEQUE_
#define _DEQUE_
#include <iterator>
#include <memory>
#include <stdexcept>
#include <xutility>

#ifdef  _MSC_VER
#pragma pack(push,8)
#endif  /* _MSC_VER */
_STD_BEGIN
#define _DEQUEMAPSIZ	2
#define _DEQUESIZ (4096 < sizeof (_Ty) ? 1 : 4096 / sizeof (_Ty))
		// TEMPLATE CLASS deque
template<class _Ty, class _A = allocator<_Ty> >
	class deque {
public:
	typedef deque<_Ty, _A> _Myt;
	typedef _A allocator_type;
	typedef _A::size_type size_type;
	typedef _A::difference_type difference_type;
	typedef _A::pointer _Tptr;
	typedef _A::const_pointer _Ctptr;
	typedef _POINTER_X(_Tptr, _A) _Mapptr;
	typedef _A::reference reference;
	typedef _A::const_reference const_reference;
	typedef _A::value_type value_type;
		// CLASS const_iterator
	class iterator;
	class const_iterator : public _Ranit<_Ty, difference_type> {
	public:
		friend class deque<_Ty, _A>;
		const_iterator()
			: _First(0), _Last(0), _Next(0), _Map(0) {}
		const_iterator(_Tptr _P, _Mapptr _M)
			: _First(*_M), _Last(*_M + _DEQUESIZ),
				_Next(_P), _Map(_M) {}
		const_iterator(const iterator& _X)
			: _First(_X._First), _Last(_X._Last), _Next(_X._Next), 
			  _Map(_X._Map) {}
		const_reference operator*() const
			{return (*_Next); }
		_Ctptr operator->() const
			{return (&**this); }
		const_iterator& operator++()
			{if (++_Next == _Last)
				{_First = *++_Map;
				_Last = _First + _DEQUESIZ;
				_Next = _First; }
			return (*this); }
		const_iterator operator++(int)
			{const_iterator _Tmp = *this;
			++*this;
			return (_Tmp); }
		const_iterator& operator--()
			{if (_Next == _First)
				{_First = *--_Map;
				_Last = _First + _DEQUESIZ;
				_Next = _Last; }
			--_Next;
			return (*this); }
		const_iterator operator--(int)
			{const_iterator _Tmp = *this;
			--*this;
			return (_Tmp); }
		const_iterator& operator+=(difference_type _N)
			{_Add(_N);
			return (*this); }
		const_iterator& operator-=(difference_type _N)
			{return (*this += -_N); }
		const_iterator operator+(difference_type _N) const
			{const_iterator _Tmp = *this;
			return (_Tmp += _N); }
		const_iterator operator-(difference_type _N) const
			{const_iterator _Tmp = *this;
			return (_Tmp -= _N); }
		difference_type operator-(const const_iterator& _X) const
			{return (_Map == _X._Map ? _Next - _X._Next
				: _DEQUESIZ * (_Map - _X._Map - 1)
				+ (_Next - _First) + (_X._Last - _X._Next)); }
		const_reference operator[](difference_type _N) const
			{return (*(*this + _N)); }
		bool operator==(const const_iterator& _X) const
			{return (_Next == _X._Next); }
		bool operator!=(const const_iterator& _X) const
			{return (!(*this == _X)); }
		bool operator<(const const_iterator& _X) const
			{return (_Map < _X._Map
				|| _Map == _X._Map && _Next < _X._Next); }
		bool operator<=(const const_iterator& _X) const
			{return (!(_X < *this)); }
		bool operator>(const const_iterator& _X) const
			{return (_X < *this); }
		bool operator>=(const const_iterator& _X) const
			{return (!(*this < _X)); }
	protected:
		void _Add(difference_type _N)
			{difference_type _Off = _N + _Next - _First;
			difference_type _Moff = (0 <= _Off)
				? _Off / _DEQUESIZ
				: -((_DEQUESIZ - 1 - _Off) / _DEQUESIZ);
			if (_Moff == 0)
				_Next += _N;
			else
				{_Map += _Moff;
				_First = *_Map;
				_Last = _First + _DEQUESIZ;
				_Next = _First + (_Off - _Moff * _DEQUESIZ); }}
	_PROTECTED:
		_Tptr _First, _Last, _Next;
		_Mapptr _Map;
		};
		// CLASS iterator
	class iterator : public const_iterator {
	public:
		iterator()
			{}
		iterator(_Tptr _P, _Mapptr _M)
			: const_iterator(_P, _M) {}
		reference operator*() const
			{return (*_Next); }
		_Tptr operator->() const
			{return (&**this); }
		iterator& operator++()
			{if (++_Next == _Last)
				{_First = *++_Map;
				_Last = _First + _DEQUESIZ;
				_Next = _First; }
			return (*this); }
		iterator operator++(int)
			{iterator _Tmp = *this;
			++*this;
			return (_Tmp); }
		iterator& operator--()
			{if (_Next == _First)
				{_First = *--_Map;
				_Last = _First + _DEQUESIZ;
				_Next = _Last; }
			--_Next;
			return (*this); }
		iterator operator--(int)
			{iterator _Tmp = *this;
			--*this;
			return (_Tmp); }
		iterator& operator+=(difference_type _N)
			{_Add(_N);
			return (*this); }
		iterator& operator-=(difference_type _N)
			{return (*this += -_N); }
		iterator operator+(difference_type _N) const
			{iterator _Tmp = *this;
			return (_Tmp += _N); }
		iterator operator-(difference_type _N) const
			{iterator _Tmp = *this;
			return (_Tmp -= _N); }
		difference_type operator-(const iterator& _X) const
			{return (_Map == _X._Map ? _Next - _X._Next
				: _DEQUESIZ * (_Map - _X._Map - 1)
				+ (_Next - _First) + (_X._Last - _X._Next)); }
		reference operator[](difference_type _N) const
			{return (*(*this + _N)); }
		bool operator==(const iterator& _X) const
			{return (_Next == _X._Next); }
		bool operator!=(const iterator& _X) const
			{return (!(*this == _X)); }
		bool operator<(const iterator& _X) const
			{return (_Map < _X._Map
				|| _Map == _X._Map && _Next < _X._Next); }
		bool operator<=(const iterator& _X) const
			{return (!(_X < *this)); }
		bool operator>(const iterator& _X) const
			{return (_X < *this); }
		bool operator>=(const iterator& _X) const
			{return (!(*this < _X)); }
		};
	typedef reverse_iterator<const_iterator, value_type,
		const_reference, _Ctptr, difference_type>
			const_reverse_iterator;
	typedef reverse_iterator<iterator, value_type,
		reference, _Tptr, difference_type>
			reverse_iterator;
	explicit deque(const _A& _Al = _A())
		: allocator(_Al),
			_First(), _Last(), _Map(0), _Mapsize(0), _Size(0)
		{}
	explicit deque(size_type _N, const _Ty& _V = _Ty(),
		const _A& _Al = _A())
		: allocator(_Al),
			_First(), _Last(), _Map(0), _Mapsize(0), _Size(0)
		{insert(begin(), _N, _V); }
	deque(const _Myt& _X)
		: allocator(_X.allocator),
			_First(), _Last(), _Map(0), _Mapsize(0), _Size(0)
		{copy(_X.begin(), _X.end(), back_inserter(*this)); }
	typedef const_iterator _It;
		deque(_It _F, _It _L, const _A& _Al = _A())
		: allocator(_Al),
			_First(), _Last(), _Map(0), _Mapsize(0), _Size(0)
		{copy(_F, _L, back_inserter(*this)); }
	~deque()
		{while (!empty())
			pop_front(); }
	_Myt& operator=(const _Myt& _X)
		{if (this != &_X)
			{iterator _S;
			if (_X.size() <= size())
				{_S = copy(_X.begin(), _X.end(), begin());
				erase(_S, end()); }
			else
				{const_iterator _Sx = _X.begin() + size();
				_S = copy(_X.begin(), _Sx, begin());
				copy(_Sx, _X.end(), inserter(*this, _S)); }}
		return (*this); }
	iterator begin()
		{return (_First); }
	const_iterator begin() const
		{return ((const_iterator)_First); }
	iterator end()
		{return (_Last); }
	const_iterator end() const
		{return ((const_iterator)_Last); }
	reverse_iterator rbegin()
		{return (reverse_iterator(end())); }
	const_reverse_iterator rbegin() const
		{return (const_reverse_iterator(end())); }
	reverse_iterator rend()
		{return (reverse_iterator(begin())); }
	const_reverse_iterator rend() const
		{return (const_reverse_iterator(begin())); }
	void resize(size_type _N, _Ty _X = _Ty())
		{if (size() < _N)
			insert(end(), _N - size(), _X);
		else if (_N < size())
			erase(begin() + _N, end()); }
	size_type size() const
		{return (_Size); }
	size_type max_size() const
		{return (allocator.max_size()); }
	bool empty() const
		{return (size() == 0); }
	_A get_allocator() const
		{return (allocator); }
	const_reference at(size_type _P) const
		{if (size() <= _P)
			_Xran();
		return (*(begin() + _P)); }
	reference at(size_type _P)
		{if (size() <= _P)
			_Xran();
		return (*(begin() + _P)); }
	const_reference operator[](size_type _P) const
		{return (*(begin() + _P)); }
	reference operator[](size_type _P)
		{return (*(begin() + _P)); }
	reference front()
		{return (*begin()); }
	const_reference front() const
		{return (*begin()); }
	reference back()
		{return (*(end() - 1)); }
	const_reference back() const
		{return (*(end() - 1)); }
	void push_front(const _Ty& _X)
		{if (empty() || _First._Next == _First._First)
			_Buyfront();
		allocator.construct(--_First._Next, _X);
		++_Size; }
	void pop_front()
		{allocator.destroy(_First._Next++);
		--_Size;
		if (empty() || _First._Next == _First._Last)
			_Freefront(); }
	void push_back(const _Ty& _X)
		{
		if (empty() || (_Last._Next == _Last._Last))
        {
            _Buyback();
            allocator.construct(_Last._Next++, _X);