#include #include #include #include #include #include using namespace std; using uint = unsigned int; using ll = long long; #define CIN( LL , A ) LL A; cin >> A #define GETLINE( A ) string A; getline( cin , A ) // 自分のライブラリ(https://github.com/p-adic/cpp)よりソースコードをコピーして編集している。 template class VLArray; template class IteratorOfVLArray; template class ConstIteratorOfVLArray; template class EntryOfVLArray { friend VLArray; friend IteratorOfVLArray; friend ConstIteratorOfVLArray; private: T m_t; EntryOfVLArray* m_prev; EntryOfVLArray* m_next; private: inline EntryOfVLArray(); template inline EntryOfVLArray( const Arg& ); template inline EntryOfVLArray( const Arg& , EntryOfVLArray* const& , EntryOfVLArray* const& ); }; template inline EntryOfVLArray::EntryOfVLArray() : m_t() , m_prev( this ) , m_next( this ) {} template template inline EntryOfVLArray::EntryOfVLArray( const Arg& t ) : m_t( t ) , m_prev( this ) , m_next( this ) {} template template inline EntryOfVLArray::EntryOfVLArray( const Arg& t , EntryOfVLArray* const& prev , EntryOfVLArray* const& next ) : m_t( t ) , m_prev( prev ) , m_next( next ) {} template class EntryOfVLArray; template class ConstIteratorOfVLArray; template class VLArray; template class IteratorOfVLArray { friend ConstIteratorOfVLArray; friend VLArray; private: // ++の実装のためにはm_pをポインタへの参照にできない。 EntryOfVLArray* m_p; public: inline IteratorOfVLArray( EntryOfVLArray* const& ) noexcept; inline IteratorOfVLArray( const IteratorOfVLArray& ) noexcept; // inline T& Access() const; inline T& operator*() const; inline T* operator->() const; IteratorOfVLArray& operator=( const IteratorOfVLArray& ) noexcept; inline void operator++( int ); inline void operator--( int ); }; template class ConstIteratorOfVLArray { friend VLArray; private: const EntryOfVLArray* m_p; public: inline ConstIteratorOfVLArray( EntryOfVLArray* const& ) noexcept; inline ConstIteratorOfVLArray( const ConstIteratorOfVLArray& ) noexcept; inline ConstIteratorOfVLArray( const IteratorOfVLArray& ) noexcept; inline const T& operator*() const; inline const T* operator->() const; ConstIteratorOfVLArray& operator=( const ConstIteratorOfVLArray& ) noexcept; ConstIteratorOfVLArray& operator=( const IteratorOfVLArray& ) noexcept; inline void operator++( int ); inline void operator--( int ); static inline bool Equal( const IteratorOfVLArray& , const IteratorOfVLArray& ) noexcept; static inline bool Equal( const ConstIteratorOfVLArray& , const IteratorOfVLArray& ) noexcept; static inline bool Equal( const IteratorOfVLArray& , const ConstIteratorOfVLArray& ) noexcept; static inline bool Equal( const ConstIteratorOfVLArray& , const ConstIteratorOfVLArray& ) noexcept; }; template inline bool operator==( const IteratorOfVLArray& , const IteratorOfVLArray& ) noexcept; template inline bool operator!=( const IteratorOfVLArray& , const IteratorOfVLArray& ) noexcept; template inline bool operator==( const ConstIteratorOfVLArray& , const IteratorOfVLArray& ) noexcept; template inline bool operator!=( const ConstIteratorOfVLArray& , const IteratorOfVLArray& ) noexcept; template inline bool operator==( const IteratorOfVLArray& , const ConstIteratorOfVLArray& ) noexcept; template inline bool operator!=( const IteratorOfVLArray& , const ConstIteratorOfVLArray& ) noexcept; template inline bool operator==( const ConstIteratorOfVLArray& , const ConstIteratorOfVLArray& ) noexcept; template inline bool operator!=( const ConstIteratorOfVLArray& , const ConstIteratorOfVLArray& ) noexcept; // IteratorOfVLArray template inline IteratorOfVLArray::IteratorOfVLArray( EntryOfVLArray* const& p ) noexcept : m_p( p ) {} template inline IteratorOfVLArray::IteratorOfVLArray( const IteratorOfVLArray& itr ) noexcept : m_p( itr.m_p ) {} // template inline T& IteratorOfVLArray::Access() const { return Access( m_p ).m_t; } template inline T& IteratorOfVLArray::operator*() const { return ( *m_p ).m_t; } template inline T* IteratorOfVLArray::operator->() const { return &( *( *this ) ); } template IteratorOfVLArray& IteratorOfVLArray::operator=( const IteratorOfVLArray& itr ) noexcept { m_p = itr.m_p; return *this; } template inline void IteratorOfVLArray::operator++( int ){ m_p = ( *m_p ).m_next; } template inline void IteratorOfVLArray::operator--( int ){ m_p = ( *m_p ).m_prev; } // ConstIteratorOfVLArray template inline ConstIteratorOfVLArray::ConstIteratorOfVLArray( EntryOfVLArray* const& p ) noexcept : m_p( p ) {} template inline ConstIteratorOfVLArray::ConstIteratorOfVLArray( const ConstIteratorOfVLArray& itr ) noexcept : m_p( itr.m_p ) {} template inline ConstIteratorOfVLArray::ConstIteratorOfVLArray( const IteratorOfVLArray& itr ) noexcept : m_p( itr.m_p ) {} template inline const T& ConstIteratorOfVLArray::operator*() const { return ( *m_p ).m_t; }; template inline const T* ConstIteratorOfVLArray::operator->() const { return &( *( *this ) ); } template ConstIteratorOfVLArray& ConstIteratorOfVLArray::operator=( const ConstIteratorOfVLArray& itr ) noexcept { m_p = itr.m_p; return *this; } template ConstIteratorOfVLArray& ConstIteratorOfVLArray::operator=( const IteratorOfVLArray& itr ) noexcept { m_p = itr.m_p; return *this; } template inline void ConstIteratorOfVLArray::operator++( int ) { m_p = ( *m_p ).m_next; } template inline void ConstIteratorOfVLArray::operator--( int ) { m_p = ( *m_p ).m_prev; } template inline bool ConstIteratorOfVLArray::Equal( const IteratorOfVLArray& itr0 , const IteratorOfVLArray& itr1 ) noexcept { return itr0.m_p == itr1.m_p; } template inline bool ConstIteratorOfVLArray::Equal( const ConstIteratorOfVLArray& itr0 , const IteratorOfVLArray& itr1 ) noexcept { return itr0.m_p == itr1.m_p; } template inline bool ConstIteratorOfVLArray::Equal( const IteratorOfVLArray& itr0 , const ConstIteratorOfVLArray& itr1 ) noexcept { return itr0.m_p == itr1.m_p; } template inline bool ConstIteratorOfVLArray::Equal( const ConstIteratorOfVLArray& itr0 , const ConstIteratorOfVLArray& itr1 ) noexcept { return itr0.m_p == itr1.m_p; } template inline bool operator==( const IteratorOfVLArray& itr0 , const IteratorOfVLArray& itr1 ) noexcept { return ConstIteratorOfVLArray::Equal( itr0 , itr1 ); } template inline bool operator!=( const IteratorOfVLArray& itr0 , const IteratorOfVLArray& itr1 ) noexcept { return !( itr0 == itr1 );} template inline bool operator==( const ConstIteratorOfVLArray& itr0 , const IteratorOfVLArray& itr1 ) noexcept { return ConstIteratorOfVLArray::Equal( itr0 , itr1 ); } template inline bool operator!=( const ConstIteratorOfVLArray& itr0 , const IteratorOfVLArray& itr1 ) noexcept { return !( itr0 == itr1 );} template inline bool operator==( const IteratorOfVLArray& itr0 , const ConstIteratorOfVLArray& itr1 ) noexcept { return ConstIteratorOfVLArray::Equal( itr0 , itr1 ); } template inline bool operator!=( const IteratorOfVLArray& itr0 , const ConstIteratorOfVLArray& itr1 ) noexcept { return !( itr0 == itr1 );} template inline bool operator==( const ConstIteratorOfVLArray& itr0 , const ConstIteratorOfVLArray& itr1 ) noexcept { return ConstIteratorOfVLArray::Equal( itr0 , itr1 ); } template inline bool operator!=( const ConstIteratorOfVLArray& itr0 , const ConstIteratorOfVLArray& itr1 ) noexcept { return !( itr0 == itr1 );} template class SingletonType { protected: SingletonType() = default; SingletonType( const SingletonType& ) = default; virtual ~SingletonType() = default; SingletonType& operator=( const SingletonType& ) = default; public: static T& GetUniqueObject(); }; template class SingletonOf : public SingletonType > { friend SingletonType >; private: SingletonOf() = default; SingletonOf( const SingletonOf& ) = default; ~SingletonOf() = default; SingletonOf& operator=( const SingletonOf& ) = default; public: using type = T; }; // Replace TYPE_NAME by a suitable typename. /* class TYPE_NAME : public SingletonType { friend SingletonType; private: TYPE_NAME() = default; TYPE_NAME( const TYPE_NAME& ) = default; ~TYPE_NAME() = default; TYPE_NAME& operator=( const TYPE_NAME& ) = default; }; */ template T& Object(); #include template T& SingletonType::GetUniqueObject() { static T t; return t; } template T& Object() { // if( ! is_base_of,T>::value ){ // ERR_IMPUT( typeid( T ) ); // } return T::GetUniqueObject(); } template class WrappedInt : public SingletonType > { friend class SingletonType >; private: WrappedInt() = default; WrappedInt( const WrappedInt& ) = default; WrappedInt& operator=( const WrappedInt& ) = default; static const int m_i; public: static int Get(); }; template class WrappedUInt : public SingletonType > { friend class SingletonType >; private: WrappedUInt() = default; WrappedUInt( const WrappedUInt& ) = default; WrappedUInt& operator=( const WrappedUInt& ) = default; static const uint m_i; public: static uint Get(); }; template const WrappedInt& Wrap(); template const WrappedUInt& WrapU(); template const int WrappedInt::m_i = i; template const uint WrappedUInt::m_i = i; template int WrappedInt::Get() { return m_i; } template uint WrappedUInt::Get() { return m_i; } template const WrappedInt& Wrap() { return Object >(); } template const WrappedUInt& WrapU() { return Object >(); } class EmptySet { private: EmptySet(); EmptySet( const EmptySet& ); EmptySet& operator=( const EmptySet& ); }; template class VLArray; template class VLMatrix_Body; template class VLMatrix_Body,T> { public: using type = VLArray; }; template class VLMatrix_Body,T> { public: using type = VLArray,T>::type>; }; template class VLMatrix_Body,T> { public: using type = VLArray,T>::type>; }; template using VLMatrix = typename VLMatrix_Body,T>::type; template class IteratorOfVLArray; template class ConstIteratorOfVLArray; template class WrappedType; template class VLArray { private: EntryOfVLArray m_e; EntryOfVLArray* const m_p_e; uint m_size; public: // Tは引数0のコンストラクタを持つクラスのみ許容。 inline VLArray(); template inline VLArray( const Arg1& , const Arg2&... ); inline VLArray( const VLArray& ); // Tが引数0のコンストラクタを持たないクラスの場合に使用。 template inline VLArray( const WrappedType& t ); virtual ~VLArray(); VLArray& operator=( const VLArray& ); inline const uint& size() const noexcept; inline void clear(); inline bool empty() const noexcept; T& front(); const T& front() const; T& back(); const T& back() const; template void push_back( const Arg& ); template void push_back( const Args&... ); template void push_front( const Arg& ); // 前から順にpush_frontする。 template void push_front( const Args&... ); void pop_back(); void pop_front(); template inline void Concatenate( const Args&... ); template void Concatenate_back( const Arg& ); template void Concatenate_back( const Args&... ); template void Concatenate_front( const Arg& ); // 前から順にConcatenate_frontする。 template void Concatenate_front( const Args&... ); using iterator = IteratorOfVLArray; using const_iterator = ConstIteratorOfVLArray; // *thisがconstである場合に確実にconst_iterator返しをするために、iterator返しは非constにする必要がある。 inline iterator begin() noexcept; inline const_iterator begin() const noexcept; inline iterator end() noexcept; inline const_iterator end() const noexcept; template void insert( const iterator& , const Arg& ); template void insert_front( const iterator& , const Arg& ); template void insert_back( const iterator& , const Arg& ); iterator erase( iterator& ); iterator erase_back( iterator& ); iterator erase_front( iterator& ); T& operator[]( const uint& ); const T& operator[]( const uint& ) const; VLArray GetInitialSegment( const int& ) const; VLArray GetFinalSegment( const int& ) const; bool CheckContain( const iterator& ) const noexcept; bool CheckContain( const const_iterator& ) const noexcept; string Display() const; private: template inline int push_back_int( const Arg& ); template inline int push_front_int( const Arg& ); template inline int Concatenate_back_int( const Arg& ); template inline int Concatenate_front_int( const Arg& ); template static inline void ExpandParameterPack( const Args&... ) noexcept; }; template bool operator==( const VLArray& , const VLArray& ); template inline bool operator!=( const VLArray& , const VLArray& ); template VLArray to_VLArray( const uint& , const T& ); template inline VLMatrix<1,T> to_VLMatrix( const uint& , const T& ); template inline VLMatrix<2,T> to_VLMatrix( const uint& , const uint& , const T& ); template inline VLMatrix<3,T> to_VLMatrix( const uint& , const uint& , const uint& , const T& ); template VLArray Frown( const Arg&... ); template T Sum( const VLArray& ); template class WrappedType { private: Arg m_t; public: template inline WrappedType( const ARGS&... args ); inline void Set( const Arg& t ); inline const Arg& Get() const noexcept; }; template class WrappedTypes {}; template template inline WrappedType::WrappedType( const ARGS&... args ) : m_t( args... ) {} template inline void WrappedType::Set( const Arg& t ){ m_t = t; } template inline const Arg& WrappedType::Get() const noexcept { return m_t; } template inline VLArray::VLArray() : m_e() , m_p_e( &m_e ) , m_size( 0 ) {} template template inline VLArray::VLArray( const Arg1& t0 , const Arg2&... t1 ) : VLArray() { push_back( t0 , t1... ); } template inline VLArray::VLArray( const VLArray& a ) : m_e( a.m_e.m_t ) , m_p_e( &m_e ) , m_size( 0 ) { Concatenate( a ); } template template inline VLArray::VLArray( const WrappedType& t ) : m_e( t.Get() ) , m_p_e( &m_e ) , m_size( 0 ) {} template VLArray::~VLArray() { clear(); } template VLArray& VLArray::operator=( const VLArray& a ) { if( this != &a ){ clear(); Concatenate( a ); } return *this; } template inline const uint& VLArray::size() const noexcept { return m_size; } template inline void VLArray::clear(){ while( m_size > 0 ) pop_back(); } template inline bool VLArray::empty() const noexcept { return m_size == 0; } template T& VLArray::front() { // if( m_size == 0 ){ // ERR_CALL; // } return m_e.m_next->m_t; } template const T& VLArray::front() const { // if( m_size == 0 ){ // ERR_CALL; // } return m_e.m_next->m_t; } template T& VLArray::back() { // if( m_size == 0 ){ // ERR_CALL; // } return m_e.m_prev->m_t; } template const T& VLArray::back() const { // if( m_size == 0 ){ // ERR_CALL; // } return m_e.m_prev->m_t; } template template void VLArray::push_back( const Arg& t ) { EntryOfVLArray* p_e_prev = m_e.m_prev; auto p = new EntryOfVLArray( t , p_e_prev , m_p_e ); m_e.m_prev = p; p_e_prev->m_next = p; m_size++; return; } template template void VLArray::push_back( const Args&... args ) { VLArray copy{}; // 関数の処理は後ろからなのでbackではなくfrontを使う。 ExpandParameterPack( copy.push_front_int( args )... ); Concatenate_back( copy ); return; } template template inline int VLArray::push_back_int( const Arg& t ) { push_back( t ); return 0; } template template void VLArray::push_front( const Arg& t ) { EntryOfVLArray* p_b = m_e.m_next; auto p = new EntryOfVLArray( t , m_p_e , p_b ); p_b->m_prev = p; m_e.m_next = p; m_size++; return; } template template void VLArray::push_front( const Args&... args ) { VLArray copy{}; // 関数の処理は後ろからなのでfrontではなくbackを使う。 ExpandParameterPack( copy.push_back_int( args )... ); Concatenate_front( copy ); return; } template template inline int VLArray::push_front_int( const Arg& t ) { push_front( t ); return 0; } template void VLArray::pop_back() { // if( m_size == 0 ){ // ERR_CALL; // } EntryOfVLArray* p_e_prev = m_e.m_prev; EntryOfVLArray* p_e_prev_prev = p_e_prev->m_prev; m_e.m_prev = p_e_prev_prev; p_e_prev_prev->m_next = m_p_e; delete p_e_prev; m_size--; return; } template void VLArray::pop_front() { // if( m_size == 0 ){ // ERR_CALL; // } EntryOfVLArray* p_b = m_e.m_next; EntryOfVLArray* p_b_next = ( *p_b ).m_next; p_b_next->m_prev = m_p_e; m_e.m_next = p_b_next; delete p_b; m_size--; return; } template template inline void VLArray::Concatenate( const Args&... args ) { Concatenate_back( args... ); } template template void VLArray::Concatenate_back( const Arg& a ) { const EntryOfVLArray* p = a.m_p_e; const uint& N = a.m_size; for( uint n = 0 ; n < N ; n++ ){ p = p->m_next; push_back( p->m_t ); } return; } template template void VLArray::Concatenate_back( const Args&... args ) { VLArray copy{}; // 関数の処理は後ろからなのでbackではなくfrontを使う。 ExpandParameterPack( copy.Concatenate_front_int( args )... ); Concatenate_back( copy ); return; } template template inline int VLArray::Concatenate_back_int( const Arg& a ) { Concatenate( a ); return 0; } template template void VLArray::Concatenate_front( const Arg& a ) { const EntryOfVLArray* p = a.m_p_e; const uint& N = a.m_size; for( uint n = 0 ; n < N ; n++ ){ p = p->m_prev; push_front( p->m_t ); } return; } template template void VLArray::Concatenate_front( const Args&... args ) { VLArray copy{}; // 関数の処理は後ろからなのでfrontではなくbackを使う。 ExpandParameterPack( copy.Concatenate_back_int( args )... ); Concatenate_front( copy ); return; } template template inline int VLArray::Concatenate_front_int( const Arg& a ) { Concatenate_front( a ); return 0; } template inline typename VLArray::iterator VLArray::begin() noexcept { return IteratorOfVLArray( m_e.m_next ); } template inline typename VLArray::const_iterator VLArray::begin() const noexcept { return ConstIteratorOfVLArray( m_e.m_next ); } template inline typename VLArray::iterator VLArray::end() noexcept { return IteratorOfVLArray( m_p_e ); } template inline typename VLArray::const_iterator VLArray::end() const noexcept { return ConstIteratorOfVLArray( m_p_e ); } template template inline void VLArray::insert( const typename VLArray::iterator& itr , const Arg& t ) { insert_back( itr , t ); } template template void VLArray::insert_front( const typename VLArray::iterator& itr , const Arg& t ) { // if( ! CheckContain( itr ) ){ // ERR_IMPUT( itr , t ); // } if( itr == begin() ){ push_front( t ); } else { EntryOfVLArray* p1 = itr.m_p; EntryOfVLArray* p0 = p1->m_prev; auto p = new EntryOfVLArray( t , p0 , p1 ); p0->m_next = p; p1->m_prev = p; m_size++; } return; } template template void VLArray::insert_back( const typename VLArray::iterator& itr , const Arg& t ) { // if( ! CheckContain( itr ) ){ // ERR_IMPUT( itr , t ); // } EntryOfVLArray* p0 = itr.m_p; EntryOfVLArray* p1 = p0->m_next; auto p = new EntryOfVLArray( t , p0 , p1 ); p1->m_prev = p; p0->m_next = p; m_size++; return; } template inline typename VLArray::iterator VLArray::erase( typename VLArray::iterator& itr ) { return erase_back( itr ); } template typename VLArray::iterator VLArray::erase_back( typename VLArray::iterator& itr ) { // if( ! CheckContain( itr ) ){ // ERR_IMPUT( itr ); // } EntryOfVLArray* p = itr.m_p; EntryOfVLArray* p0 = p->m_prev; EntryOfVLArray* p1 = p->m_next; p0->m_next = p1; p1->m_prev = p0; itr++; delete p; m_size--; return itr; } template typename VLArray::iterator VLArray::erase_front( typename VLArray::iterator& itr ) { // if( ! CheckContain( itr ) ){ // ERR_IMPUT( itr ); // } EntryOfVLArray* p = itr.m_p; EntryOfVLArray* p0 = p->m_prev; EntryOfVLArray* p1 = p->m_next; p0->m_next = p1; p1->m_prev = p0; itr--; delete p; m_size--; return itr; } template T& VLArray::operator[]( const uint& i ) { // if( i >= m_size ){ // ERR_IMPUT( i ); // } if( i < m_size / 2 ){ EntryOfVLArray* p = m_e.m_next; for( uint n = 0 ; n < i ; n++ ){ p = p->m_next; } return p->m_t; } EntryOfVLArray* p = m_e.m_prev; for( uint n = m_size - 1 ; n > i ; n-- ){ p = p->m_prev; } return p->m_t; } template const T& VLArray::operator[]( const uint& i ) const { // if( i >= m_size ){ // ERR_IMPUT( i ); // } if( i < m_size / 2 ){ EntryOfVLArray* p = m_e.m_next; for( uint n = 0 ; n < i ; n++ ){ p = p->m_next; } return p->m_t; } EntryOfVLArray* p = m_e.m_prev; for( uint n = m_size - 1 ; n > i ; n-- ){ p = p->m_prev; } return p->m_t; } template VLArray VLArray::GetInitialSegment( const int& n ) const { const int N = (int)m_size; int M; if( N <= n ){ M = N; } else { if( 0 <= n ){ M = n; } else { M = N + n; } } VLArray b{}; const_iterator itr = begin(); for( int m = 1 ; m <= M ; m++ ){ b.push_back( *itr ); itr++; } return b; } template VLArray VLArray::GetFinalSegment( const int& n ) const { const int N = (int)m_size; int M; if( N <= n ){ M = N; } else { if( 0 <= n ){ M = n; } else { M = N + n; } } VLArray b{}; const_iterator itr = end(); for( int m = 1 ; m <= M ; m++ ){ itr--; b.push_front( *itr ); } return b; } template bool VLArray::CheckContain( const iterator& itr ) const noexcept { for( auto itr_b = begin() , itr_e = end() ; itr_b != itr_e ; itr_b++ ){ if( itr == itr_b ){ return true; } } return false; } template bool VLArray::CheckContain( const const_iterator& itr ) const noexcept { for( auto itr_b = begin() , itr_e = end() ; itr_b != itr_e ; itr_b++ ){ if( itr == itr_b ){ return true; } } return false; } template string VLArray::Display() const { string s = "("; EntryOfVLArray* p = m_p_e; for( uint n = 0 ; n < m_size ; n++ ){ p = p->m_next; if( n > 0 ){ s += ","; } s += to_string( p->m_t ); } s += ")"; return s; } template template inline void VLArray::ExpandParameterPack( const Args&... ) noexcept {}; template bool operator==( const VLArray& a1 , const VLArray& a2 ) { auto itr1 = a1.begin(); auto end1 = a1.end(); auto itr2 = a2.begin(); auto end2 = a2.end(); while( itr1 != end1 && itr2 != end2 ){ if( *itr1 != *itr2 ){ return false; } itr1++; itr2++; } return ( itr1 == end1 ) && ( itr2 == end2 ); } template inline bool operator!=( const VLArray& a1 , const VLArray& a2 ) { return !( a1 == a2 ); } template VLArray to_VLArray( const uint& N , const T& t ) { auto a = VLArray(); for( uint n = 0 ; n < N ; n++ ){ a.push_back( t ); } return a; } template inline VLMatrix<1,T> to_VLMatrix( const uint& N , const T& t ){ return to_VLArray( N , t ); } template inline VLMatrix<2,T> to_VLMatrix( const uint& N0 , const uint& N1 , const T& t ){ return to_VLArray( N1 , to_VLArray( N0 , t ) ); } template inline VLMatrix<3,T> to_VLMatrix( const uint& N0 , const uint& N1 , const uint& N2 , const T& t){ return to_VLArray( N2 , to_VLMatrix( N0 , N1 , t ) ); } template VLArray Frown( const Arg&... args ) { VLArray a{}; a.Concatenate( args... ); return a; } template T Sum( const VLArray& a ) { T t{}; for( auto itr = a.begin() , end = a.end() ; itr != end ; itr++ ){ t += *itr; } return t; } template void Sort( VLArray& a , const string& method = "normal" , const VLArray& option = VLArray() ); template void NormalSort( VLArray& a , const VLArray& option = VLArray() ); template void NormalSortNoCut( VLArray& a ); template void NormalSortCut( VLArray& a , const uint& cut_length , const bool& cut_large ); template void MergeSort( VLArray& a , const VLArray& option = VLArray() ); template void MergeSortNoCut( VLArray& a ); template void MergeSortCut( VLArray& a , const uint& cut_length , const bool& cut_large , const uint& normal_method_length = 2 ); template void Sort( VLArray& a , const string& method , const VLArray& option ) { if( method == "merge" ){ MergeSort( a , option ); } else { NormalSort( a , option ); } return; } template void NormalSort( VLArray& a , const VLArray& option ) { if( ! option.empty() ){ const uint& cut_length_signed = option[0]; if( cut_length_signed != 0 ){ if( cut_length_signed > 0 ){ NormalSortCut( a , (uint)cut_length_signed , true ); } else { NormalSortCut( a , (uint)( - cut_length_signed ) , false ); } return; } } NormalSortNoCut( a ); return; } template void NormalSortNoCut( VLArray& a ) { auto itr0 = a.begin() , end0 = a.end(); while( itr0 != end0 ){ const T& t = *itr0; auto itr1 = itr0; itr1--; auto itr_ins = end0; bool changing = false; while( itr1 != end0 ){ if( *itr1 > t ){ if( ! changing ){ changing = true; } itr1--; } else { if( changing ){ itr_ins = itr1; } itr1 = end0; } } if( changing ){ a.insert_back( itr_ins , t ); a.erase_back( itr0 ); } else { itr0++; } } return; } template void NormalSortCut( VLArray& a , const uint& cut_length , const bool& cut_large ) { using type = typename VLArray::iterator; using incr_type = void( type::* )( int ); using ins_type = void( VLArray::* )( const type& , const T& ); using er_type = type( VLArray::* )( type& ); uint length = 0; type itr0 = a.end() , end0 = itr0; incr_type incr; incr_type decr; ins_type ins; er_type er; if( cut_large ){ itr0 = a.begin(); incr = &type::operator++; decr = &type::operator--; ins = &VLArray::insert_back; er = &VLArray::erase_back; } else { itr0--; incr = &type::operator--; decr = &type::operator++; ins = &VLArray::insert_front; er = &VLArray::erase_front; } while( itr0 != end0 ){ const T& t = *itr0; auto itr1 = itr0; ( itr1.*decr )( 0 ); auto itr_ins = end0; bool changing = false; while( itr1 != end0 ){ if( *itr1 > t ){ if( ! changing ){ changing = true; } ( itr1.*decr )( 0 ); } else { if( changing ){ itr_ins = itr1; } itr1 = end0; } } if( changing ){ ( a.*ins )( itr_ins , t ); ( a.*er )( itr0 ); if( length < cut_length ){ length++; } else { auto itr2 = itr0; ( itr2.*decr )( 0 ); ( a.*er )( itr2 ); } } else { ( itr0.*incr )( 0 ); } } return; } template void MergeSort( VLArray& a , const VLArray& option ) { const uint& size = option.size(); if( size > 0 ){ const uint& cut_length_signed = option[0]; if( cut_length_signed != 0 ){ uint cut_length; bool cut_large; if( cut_length_signed > 0 ){ cut_length = (uint)cut_length_signed; cut_large = true; } else { cut_length = (uint)( - cut_length_signed ); cut_large = false; } if( size > 1 ){ const int& normal_method_length = option[1]; if( normal_method_length > 0 ){ MergeSortCut( a , cut_length , cut_large , (uint)( normal_method_length ) ); return; } } MergeSortCut( a , cut_length , cut_large ); return; } } MergeSortNoCut( a ); return; } template void MergeSortNoCut( VLArray& a ) { const uint& size_a = a.size(); if( size_a <= 2 ){ NormalSortNoCut( a ); return; } const uint half_size_a = size_a / 2; auto itr = a.begin(); VLArray b{}; for( uint i = 0 ; i < half_size_a ; i++ ){ b.push_back( *itr ); a.erase( itr ); } MergeSortNoCut( a ); MergeSortNoCut( b ); itr = a.begin(); auto end = a.end(); const uint& size_b = b.size(); while( size_b != 0 ){ const T& t = b.front(); bool not_inserted = true; while( itr != end && not_inserted ){ if( t < *itr ){ a.insert_front( itr , t ); not_inserted = false; } else { itr++; } } if( not_inserted ){ a.push_back( t ); } b.pop_front(); } return; } template void MergeSortCut( VLArray& a , const uint& cut_length , const bool& cut_large , const uint& normal_method_length ) { const uint& size_a = a.size(); if( size_a <= normal_method_length ){ if( size_a <= cut_length ){ NormalSortNoCut( a ); } else { NormalSortCut( a , cut_length , cut_large ); } return; } const uint half_size_a = size_a / 2; using type = typename VLArray::iterator; type itr = a.begin(); VLArray b{}; for( uint i = 0 ; i < half_size_a ; i++ ){ b.push_back( *itr ); a.erase( itr ); } MergeSortCut( a , cut_length , cut_large , normal_method_length ); MergeSortCut( b , cut_length , cut_large , normal_method_length ); uint i = 0; type end = a.end(); const uint& size_b = b.size(); using incr_type = void( type::* )( int ); using front_type = const T&( VLArray::* )() const; using ins_type = void( VLArray::* )( const type& , const T& ); using push_type = void( VLArray::* )( const T& ); using pop_type = void( VLArray::* )(); incr_type incr; front_type fr; ins_type ins; push_type push; pop_type pop_fr; pop_type pop_ba; if( cut_large ){ itr = a.begin(); fr = &VLArray::front; incr = &type::operator++; ins = &VLArray::insert_front; push = &VLArray::push_back; pop_fr = &VLArray::pop_front; pop_ba = &VLArray::pop_back; } else { itr = end; itr--; fr = &VLArray::back; incr = &type::operator--; ins = &VLArray::insert_back; push = &VLArray::push_front; pop_fr = &VLArray::pop_back; pop_ba = &VLArray::pop_front; } while( size_b != 0 && i <= cut_length ){ const T& t = ( b.*fr )(); bool not_inserted = true; while( itr != end && not_inserted ){ if( t < *itr ){ ( a.*ins )( itr , t ); not_inserted = false; } else { ( itr.*incr )( 0 ); } i++; } if( not_inserted ){ ( a.*push )( t ); } ( b.*pop_fr )(); } while( size_a > cut_length ){ ( a.*pop_ba )(); } return; } int main() { CIN( ll , N ); ll x; VLArray X{}; for( ll i = 0 ; i < N ; i++ ){ cin >> x; X.push_back( x ); } Sort( X , "merge" ); ll answer = 0; auto itr0 = X.begin() , itr1 = itr0 , end = X.end(); itr1++; while( itr1 != end ){ const ll d = *itr1 - *itr0; if( d != 0 ){ if( answer == 0 || d < answer ){ answer = d; } } itr0++; itr1++; } cout << answer << endl; return 0; }