結果
問題 | No.275 中央値を求めよ |
ユーザー |
👑 |
提出日時 | 2022-08-08 23:05:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 27 ms / 1,000 ms |
コード長 | 35,299 bytes |
コンパイル時間 | 994 ms |
コンパイル使用メモリ | 78,472 KB |
最終ジャッジ日時 | 2025-01-30 19:32:13 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include <iostream>#include <list>#include <vector>#include <string>#include <stdio.h>#include <stdint.h>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 <typename T> class VLArray;template <typename T> class IteratorOfVLArray;template <typename T> class ConstIteratorOfVLArray;template <typename T>class EntryOfVLArray{friend VLArray<T>;friend IteratorOfVLArray<T>;friend ConstIteratorOfVLArray<T>;private:T m_t;EntryOfVLArray<T>* m_prev;EntryOfVLArray<T>* m_next;private:inline EntryOfVLArray();template <typename Arg> inline EntryOfVLArray( const Arg& );template <typename Arg> inline EntryOfVLArray( const Arg& , EntryOfVLArray<T>* const& , EntryOfVLArray<T>* const& );};template <typename T> inline EntryOfVLArray<T>::EntryOfVLArray() : m_t() , m_prev( this ) , m_next( this ) {}template <typename T> template <typename Arg> inline EntryOfVLArray<T>::EntryOfVLArray( const Arg& t ) : m_t( t ) , m_prev( this ) , m_next( this ){}template <typename T> template <typename Arg> inline EntryOfVLArray<T>::EntryOfVLArray( const Arg& t , EntryOfVLArray<T>* const& prev ,EntryOfVLArray<T>* const& next ) : m_t( t ) , m_prev( prev ) , m_next( next ) {}template <typename T> class EntryOfVLArray;template <typename T> class ConstIteratorOfVLArray;template <typename T> class VLArray;template <typename T>class IteratorOfVLArray{friend ConstIteratorOfVLArray<T>;friend VLArray<T>;private:// ++の実装のためにはm_pをポインタへの参照にできない。EntryOfVLArray<T>* m_p;public:inline IteratorOfVLArray( EntryOfVLArray<T>* const& ) noexcept;inline IteratorOfVLArray( const IteratorOfVLArray<T>& ) noexcept;// inline T& Access() const;inline T& operator*() const;inline T* operator->() const;IteratorOfVLArray<T>& operator=( const IteratorOfVLArray<T>& ) noexcept;inline void operator++( int );inline void operator--( int );};template <typename T>class ConstIteratorOfVLArray{friend VLArray<T>;private:const EntryOfVLArray<T>* m_p;public:inline ConstIteratorOfVLArray( EntryOfVLArray<T>* const& ) noexcept;inline ConstIteratorOfVLArray( const ConstIteratorOfVLArray<T>& ) noexcept;inline ConstIteratorOfVLArray( const IteratorOfVLArray<T>& ) noexcept;inline const T& operator*() const;inline const T* operator->() const;ConstIteratorOfVLArray<T>& operator=( const ConstIteratorOfVLArray<T>& ) noexcept;ConstIteratorOfVLArray<T>& operator=( const IteratorOfVLArray<T>& ) noexcept;inline void operator++( int );inline void operator--( int );static inline bool Equal( const IteratorOfVLArray<T>& , const IteratorOfVLArray<T>& ) noexcept;static inline bool Equal( const ConstIteratorOfVLArray<T>& , const IteratorOfVLArray<T>& ) noexcept;static inline bool Equal( const IteratorOfVLArray<T>& , const ConstIteratorOfVLArray<T>& ) noexcept;static inline bool Equal( const ConstIteratorOfVLArray<T>& , const ConstIteratorOfVLArray<T>& ) noexcept;};template <typename T> inline bool operator==( const IteratorOfVLArray<T>& , const IteratorOfVLArray<T>& ) noexcept;template <typename T> inline bool operator!=( const IteratorOfVLArray<T>& , const IteratorOfVLArray<T>& ) noexcept;template <typename T> inline bool operator==( const ConstIteratorOfVLArray<T>& , const IteratorOfVLArray<T>& ) noexcept;template <typename T> inline bool operator!=( const ConstIteratorOfVLArray<T>& , const IteratorOfVLArray<T>& ) noexcept;template <typename T> inline bool operator==( const IteratorOfVLArray<T>& , const ConstIteratorOfVLArray<T>& ) noexcept;template <typename T> inline bool operator!=( const IteratorOfVLArray<T>& , const ConstIteratorOfVLArray<T>& ) noexcept;template <typename T> inline bool operator==( const ConstIteratorOfVLArray<T>& , const ConstIteratorOfVLArray<T>& ) noexcept;template <typename T> inline bool operator!=( const ConstIteratorOfVLArray<T>& , const ConstIteratorOfVLArray<T>& ) noexcept;// IteratorOfVLArraytemplate <typename T> inline IteratorOfVLArray<T>::IteratorOfVLArray( EntryOfVLArray<T>* const& p ) noexcept : m_p( p ) {}template <typename T> inline IteratorOfVLArray<T>::IteratorOfVLArray( const IteratorOfVLArray<T>& itr ) noexcept : m_p( itr.m_p ) {}// template <typename T> inline T& IteratorOfVLArray<T>::Access() const { return Access( m_p ).m_t; }template <typename T> inline T& IteratorOfVLArray<T>::operator*() const { return ( *m_p ).m_t; }template <typename T> inline T* IteratorOfVLArray<T>::operator->() const { return &( *( *this ) ); }template <typename T>IteratorOfVLArray<T>& IteratorOfVLArray<T>::operator=( const IteratorOfVLArray<T>& itr ) noexcept{m_p = itr.m_p;return *this;}template <typename T> inline void IteratorOfVLArray<T>::operator++( int ){ m_p = ( *m_p ).m_next; }template <typename T> inline void IteratorOfVLArray<T>::operator--( int ){ m_p = ( *m_p ).m_prev; }// ConstIteratorOfVLArraytemplate <typename T> inline ConstIteratorOfVLArray<T>::ConstIteratorOfVLArray( EntryOfVLArray<T>* const& p ) noexcept : m_p( p ) {}template <typename T> inline ConstIteratorOfVLArray<T>::ConstIteratorOfVLArray( const ConstIteratorOfVLArray<T>& itr ) noexcept : m_p( itr.m_p ) {}template <typename T> inline ConstIteratorOfVLArray<T>::ConstIteratorOfVLArray( const IteratorOfVLArray<T>& itr ) noexcept : m_p( itr.m_p ) {}template <typename T> inline const T& ConstIteratorOfVLArray<T>::operator*() const { return ( *m_p ).m_t; };template <typename T> inline const T* ConstIteratorOfVLArray<T>::operator->() const { return &( *( *this ) ); }template <typename T>ConstIteratorOfVLArray<T>& ConstIteratorOfVLArray<T>::operator=( const ConstIteratorOfVLArray<T>& itr ) noexcept{m_p = itr.m_p;return *this;}template <typename T>ConstIteratorOfVLArray<T>& ConstIteratorOfVLArray<T>::operator=( const IteratorOfVLArray<T>& itr ) noexcept{m_p = itr.m_p;return *this;}template <typename T> inline void ConstIteratorOfVLArray<T>::operator++( int ) { m_p = ( *m_p ).m_next; }template <typename T> inline void ConstIteratorOfVLArray<T>::operator--( int ) { m_p = ( *m_p ).m_prev; }template <typename T> inline bool ConstIteratorOfVLArray<T>::Equal( const IteratorOfVLArray<T>& itr0 , const IteratorOfVLArray<T>& itr1 ) noexcept {return itr0.m_p == itr1.m_p; }template <typename T> inline bool ConstIteratorOfVLArray<T>::Equal( const ConstIteratorOfVLArray<T>& itr0 , const IteratorOfVLArray<T>& itr1 )noexcept { return itr0.m_p == itr1.m_p; }template <typename T> inline bool ConstIteratorOfVLArray<T>::Equal( const IteratorOfVLArray<T>& itr0 , const ConstIteratorOfVLArray<T>& itr1 )noexcept { return itr0.m_p == itr1.m_p; }template <typename T> inline bool ConstIteratorOfVLArray<T>::Equal( const ConstIteratorOfVLArray<T>& itr0 , const ConstIteratorOfVLArray<T>& itr1 )noexcept { return itr0.m_p == itr1.m_p; }template <typename T> inline bool operator==( const IteratorOfVLArray<T>& itr0 , const IteratorOfVLArray<T>& itr1 ) noexcept { returnConstIteratorOfVLArray<T>::Equal( itr0 , itr1 ); }template <typename T> inline bool operator!=( const IteratorOfVLArray<T>& itr0 , const IteratorOfVLArray<T>& itr1 ) noexcept { return !( itr0 ==itr1 );}template <typename T> inline bool operator==( const ConstIteratorOfVLArray<T>& itr0 , const IteratorOfVLArray<T>& itr1 ) noexcept { returnConstIteratorOfVLArray<T>::Equal( itr0 , itr1 ); }template <typename T> inline bool operator!=( const ConstIteratorOfVLArray<T>& itr0 , const IteratorOfVLArray<T>& itr1 ) noexcept { return !( itr0== itr1 );}template <typename T> inline bool operator==( const IteratorOfVLArray<T>& itr0 , const ConstIteratorOfVLArray<T>& itr1 ) noexcept { returnConstIteratorOfVLArray<T>::Equal( itr0 , itr1 ); }template <typename T> inline bool operator!=( const IteratorOfVLArray<T>& itr0 , const ConstIteratorOfVLArray<T>& itr1 ) noexcept { return !( itr0== itr1 );}template <typename T> inline bool operator==( const ConstIteratorOfVLArray<T>& itr0 , const ConstIteratorOfVLArray<T>& itr1 ) noexcept { returnConstIteratorOfVLArray<T>::Equal( itr0 , itr1 ); }template <typename T> inline bool operator!=( const ConstIteratorOfVLArray<T>& itr0 , const ConstIteratorOfVLArray<T>& itr1 ) noexcept { return !(itr0 == itr1 );}template <typename T>class SingletonType{protected:SingletonType() = default;SingletonType( const SingletonType& ) = default;virtual ~SingletonType() = default;SingletonType& operator=( const SingletonType& ) = default;public:static T& GetUniqueObject();};template <typename T>class SingletonOf :public SingletonType<SingletonOf<T> >{friend SingletonType<SingletonOf<T> >;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<TYPE_NAME>{friend SingletonType<TYPE_NAME>;private:TYPE_NAME() = default;TYPE_NAME( const TYPE_NAME& ) = default;~TYPE_NAME() = default;TYPE_NAME& operator=( const TYPE_NAME& ) = default;};*/template <typename T> T& Object();#include <typeinfo>template <typename T>T& SingletonType<T>::GetUniqueObject(){static T t;return t;}template <typename T>T& Object(){// if( ! is_base_of<SingletonType<T>,T>::value ){// ERR_IMPUT( typeid( T ) );// }return T::GetUniqueObject();}template <int i>class WrappedInt :public SingletonType<WrappedInt<i> >{friend class SingletonType<WrappedInt<i> >;private:WrappedInt() = default;WrappedInt( const WrappedInt& ) = default;WrappedInt& operator=( const WrappedInt& ) = default;static const int m_i;public:static int Get();};template <uint i>class WrappedUInt :public SingletonType<WrappedUInt<i> >{friend class SingletonType<WrappedUInt<i> >;private:WrappedUInt() = default;WrappedUInt( const WrappedUInt& ) = default;WrappedUInt& operator=( const WrappedUInt& ) = default;static const uint m_i;public:static uint Get();};template <int i> const WrappedInt<i>& Wrap();template <uint i> const WrappedUInt<i>& WrapU();template <int i>const int WrappedInt<i>::m_i = i;template <uint i>const uint WrappedUInt<i>::m_i = i;template <int i>int WrappedInt<i>::Get(){return m_i;}template <uint i>uint WrappedUInt<i>::Get(){return m_i;}template <int i>const WrappedInt<i>& Wrap(){return Object<WrappedInt<i> >();}template <uint i>const WrappedUInt<i>& WrapU(){return Object<WrappedUInt<i> >();}class EmptySet{private:EmptySet();EmptySet( const EmptySet& );EmptySet& operator=( const EmptySet& );};template <typename T> class VLArray;template <typename N , typename T> class VLMatrix_Body;template <typename T>class VLMatrix_Body<WrappedUInt<1>,T>{public:using type = VLArray<T>;};template <typename T>class VLMatrix_Body<WrappedUInt<2>,T>{public:using type = VLArray<typename VLMatrix_Body<WrappedUInt<1>,T>::type>;};template <typename T>class VLMatrix_Body<WrappedUInt<3>,T>{public:using type = VLArray<typename VLMatrix_Body<WrappedUInt<2>,T>::type>;};template <uint N , typename T>using VLMatrix = typename VLMatrix_Body<WrappedUInt<N>,T>::type;template <typename T> class IteratorOfVLArray;template <typename T> class ConstIteratorOfVLArray;template <typename Arg> class WrappedType;template <typename T>class VLArray{private:EntryOfVLArray<T> m_e;EntryOfVLArray<T>* const m_p_e;uint m_size;public:// Tは引数0のコンストラクタを持つクラスのみ許容。inline VLArray();template <typename Arg1 , typename... Arg2> inline VLArray( const Arg1& , const Arg2&... );inline VLArray( const VLArray<T>& );// Tが引数0のコンストラクタを持たないクラスの場合に使用。template <typename Arg> inline VLArray( const WrappedType<Arg>& t );virtual ~VLArray();VLArray<T>& operator=( const VLArray<T>& );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 <typename Arg> void push_back( const Arg& );template <typename... Args> void push_back( const Args&... );template <typename Arg> void push_front( const Arg& );// 前から順にpush_frontする。template <typename... Args> void push_front( const Args&... );void pop_back();void pop_front();template <typename... Args> inline void Concatenate( const Args&... );template <typename Arg> void Concatenate_back( const Arg& );template <typename... Args> void Concatenate_back( const Args&... );template <typename Arg> void Concatenate_front( const Arg& );// 前から順にConcatenate_frontする。template <typename... Args> void Concatenate_front( const Args&... );using iterator = IteratorOfVLArray<T>;using const_iterator = ConstIteratorOfVLArray<T>;// *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 <typename Arg> void insert( const iterator& , const Arg& );template <typename Arg> void insert_front( const iterator& , const Arg& );template <typename Arg> 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<T> GetInitialSegment( const int& ) const;VLArray<T> GetFinalSegment( const int& ) const;bool CheckContain( const iterator& ) const noexcept;bool CheckContain( const const_iterator& ) const noexcept;string Display() const;private:template <typename Arg> inline int push_back_int( const Arg& );template <typename Arg> inline int push_front_int( const Arg& );template <typename Arg> inline int Concatenate_back_int( const Arg& );template <typename Arg> inline int Concatenate_front_int( const Arg& );template <typename... Args> static inline void ExpandParameterPack( const Args&... ) noexcept;};template <typename T> bool operator==( const VLArray<T>& , const VLArray<T>& );template <typename T> inline bool operator!=( const VLArray<T>& , const VLArray<T>& );template <typename T> VLArray<T> to_VLArray( const uint& , const T& );template <typename T> inline VLMatrix<1,T> to_VLMatrix( const uint& , const T& );template <typename T> inline VLMatrix<2,T> to_VLMatrix( const uint& , const uint& , const T& );template <typename T> inline VLMatrix<3,T> to_VLMatrix( const uint& , const uint& , const uint& , const T& );template <typename T , typename... Arg> VLArray<T> Frown( const Arg&... );template <typename T> T Sum( const VLArray<T>& );template <typename Arg>class WrappedType{private:Arg m_t;public:template <typename... ARGS> inline WrappedType( const ARGS&... args );inline void Set( const Arg& t );inline const Arg& Get() const noexcept;};template <typename... Types>class WrappedTypes{};template <typename Arg> template <typename... ARGS> inline WrappedType<Arg>::WrappedType( const ARGS&... args ) : m_t( args... ) {}template <typename Arg> inline void WrappedType<Arg>::Set( const Arg& t ){ m_t = t; }template <typename Arg> inline const Arg& WrappedType<Arg>::Get() const noexcept { return m_t; }template <typename T> inline VLArray<T>::VLArray() : m_e() , m_p_e( &m_e ) , m_size( 0 ) {}template <typename T> template <typename Arg1 , typename... Arg2> inline VLArray<T>::VLArray( const Arg1& t0 , const Arg2&... t1 ) : VLArray() {push_back( t0 , t1... ); }template <typename T> inline VLArray<T>::VLArray( const VLArray<T>& a ) : m_e( a.m_e.m_t ) , m_p_e( &m_e ) , m_size( 0 ) { Concatenate( a ); }template <typename T> template <typename Arg> inline VLArray<T>::VLArray( const WrappedType<Arg>& t ) : m_e( t.Get() ) , m_p_e( &m_e ) , m_size( 0 ){}template <typename T> VLArray<T>::~VLArray() { clear(); }template <typename T>VLArray<T>& VLArray<T>::operator=( const VLArray<T>& a ){if( this != &a ){clear();Concatenate( a );}return *this;}template <typename T> inline const uint& VLArray<T>::size() const noexcept { return m_size; }template <typename T> inline void VLArray<T>::clear(){ while( m_size > 0 ) pop_back(); }template <typename T> inline bool VLArray<T>::empty() const noexcept { return m_size == 0; }template <typename T>T& VLArray<T>::front(){// if( m_size == 0 ){// ERR_CALL;// }return m_e.m_next->m_t;}template <typename T>const T& VLArray<T>::front() const{// if( m_size == 0 ){// ERR_CALL;// }return m_e.m_next->m_t;}template <typename T>T& VLArray<T>::back(){// if( m_size == 0 ){// ERR_CALL;// }return m_e.m_prev->m_t;}template <typename T>const T& VLArray<T>::back() const{// if( m_size == 0 ){// ERR_CALL;// }return m_e.m_prev->m_t;}template <typename T> template <typename Arg>void VLArray<T>::push_back( const Arg& t ){EntryOfVLArray<T>* p_e_prev = m_e.m_prev;auto p = new EntryOfVLArray<T>( t , p_e_prev , m_p_e );m_e.m_prev = p;p_e_prev->m_next = p;m_size++;return;}template <typename T> template <typename... Args>void VLArray<T>::push_back( const Args&... args ){VLArray<T> copy{};// 関数の処理は後ろからなのでbackではなくfrontを使う。ExpandParameterPack( copy.push_front_int( args )... );Concatenate_back( copy );return;}template <typename T> template <typename Arg> inline int VLArray<T>::push_back_int( const Arg& t ) { push_back( t ); return 0; }template <typename T> template <typename Arg>void VLArray<T>::push_front( const Arg& t ){EntryOfVLArray<T>* p_b = m_e.m_next;auto p = new EntryOfVLArray<T>( t , m_p_e , p_b );p_b->m_prev = p;m_e.m_next = p;m_size++;return;}template <typename T> template <typename... Args>void VLArray<T>::push_front( const Args&... args ){VLArray<T> copy{};// 関数の処理は後ろからなのでfrontではなくbackを使う。ExpandParameterPack( copy.push_back_int( args )... );Concatenate_front( copy );return;}template <typename T> template <typename Arg> inline int VLArray<T>::push_front_int( const Arg& t ) { push_front( t ); return 0; }template <typename T>void VLArray<T>::pop_back(){// if( m_size == 0 ){// ERR_CALL;// }EntryOfVLArray<T>* p_e_prev = m_e.m_prev;EntryOfVLArray<T>* 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 <typename T>void VLArray<T>::pop_front(){// if( m_size == 0 ){// ERR_CALL;// }EntryOfVLArray<T>* p_b = m_e.m_next;EntryOfVLArray<T>* 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 <typename T> template <typename... Args> inline void VLArray<T>::Concatenate( const Args&... args ) { Concatenate_back( args... ); }template <typename T> template <typename Arg>void VLArray<T>::Concatenate_back( const Arg& a ){const EntryOfVLArray<T>* 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 <typename T> template <typename... Args>void VLArray<T>::Concatenate_back( const Args&... args ){VLArray<T> copy{};// 関数の処理は後ろからなのでbackではなくfrontを使う。ExpandParameterPack( copy.Concatenate_front_int( args )... );Concatenate_back( copy );return;}template <typename T> template <typename Arg> inline int VLArray<T>::Concatenate_back_int( const Arg& a ) { Concatenate( a ); return 0; }template <typename T> template <typename Arg>void VLArray<T>::Concatenate_front( const Arg& a ){const EntryOfVLArray<T>* 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 <typename T> template <typename... Args>void VLArray<T>::Concatenate_front( const Args&... args ){VLArray<T> copy{};// 関数の処理は後ろからなのでfrontではなくbackを使う。ExpandParameterPack( copy.Concatenate_back_int( args )... );Concatenate_front( copy );return;}template <typename T> template <typename Arg> inline int VLArray<T>::Concatenate_front_int( const Arg& a ) { Concatenate_front( a ); return 0; }template <typename T> inline typename VLArray<T>::iterator VLArray<T>::begin() noexcept { return IteratorOfVLArray<T>( m_e.m_next ); }template <typename T> inline typename VLArray<T>::const_iterator VLArray<T>::begin() const noexcept { return ConstIteratorOfVLArray<T>( m_e.m_next); }template <typename T> inline typename VLArray<T>::iterator VLArray<T>::end() noexcept { return IteratorOfVLArray<T>( m_p_e ); }template <typename T> inline typename VLArray<T>::const_iterator VLArray<T>::end() const noexcept { return ConstIteratorOfVLArray<T>( m_p_e ); }template <typename T> template <typename Arg> inline void VLArray<T>::insert( const typename VLArray<T>::iterator& itr , const Arg& t ) {insert_back( itr , t ); }template <typename T> template <typename Arg>void VLArray<T>::insert_front( const typename VLArray<T>::iterator& itr , const Arg& t ){// if( ! CheckContain( itr ) ){// ERR_IMPUT( itr , t );// }if( itr == begin() ){push_front( t );} else {EntryOfVLArray<T>* p1 = itr.m_p;EntryOfVLArray<T>* p0 = p1->m_prev;auto p = new EntryOfVLArray<T>( t , p0 , p1 );p0->m_next = p;p1->m_prev = p;m_size++;}return;}template <typename T> template <typename Arg>void VLArray<T>::insert_back( const typename VLArray<T>::iterator& itr , const Arg& t ){// if( ! CheckContain( itr ) ){// ERR_IMPUT( itr , t );// }EntryOfVLArray<T>* p0 = itr.m_p;EntryOfVLArray<T>* p1 = p0->m_next;auto p = new EntryOfVLArray<T>( t , p0 , p1 );p1->m_prev = p;p0->m_next = p;m_size++;return;}template <typename T> inline typename VLArray<T>::iterator VLArray<T>::erase( typename VLArray<T>::iterator& itr ) { return erase_back( itr ); }template <typename T>typename VLArray<T>::iterator VLArray<T>::erase_back( typename VLArray<T>::iterator& itr ){// if( ! CheckContain( itr ) ){// ERR_IMPUT( itr );// }EntryOfVLArray<T>* p = itr.m_p;EntryOfVLArray<T>* p0 = p->m_prev;EntryOfVLArray<T>* p1 = p->m_next;p0->m_next = p1;p1->m_prev = p0;itr++;delete p;m_size--;return itr;}template <typename T>typename VLArray<T>::iterator VLArray<T>::erase_front( typename VLArray<T>::iterator& itr ){// if( ! CheckContain( itr ) ){// ERR_IMPUT( itr );// }EntryOfVLArray<T>* p = itr.m_p;EntryOfVLArray<T>* p0 = p->m_prev;EntryOfVLArray<T>* p1 = p->m_next;p0->m_next = p1;p1->m_prev = p0;itr--;delete p;m_size--;return itr;}template <typename T>T& VLArray<T>::operator[]( const uint& i ){// if( i >= m_size ){// ERR_IMPUT( i );// }if( i < m_size / 2 ){EntryOfVLArray<T>* p = m_e.m_next;for( uint n = 0 ; n < i ; n++ ){p = p->m_next;}return p->m_t;}EntryOfVLArray<T>* p = m_e.m_prev;for( uint n = m_size - 1 ; n > i ; n-- ){p = p->m_prev;}return p->m_t;}template <typename T>const T& VLArray<T>::operator[]( const uint& i ) const{// if( i >= m_size ){// ERR_IMPUT( i );// }if( i < m_size / 2 ){EntryOfVLArray<T>* p = m_e.m_next;for( uint n = 0 ; n < i ; n++ ){p = p->m_next;}return p->m_t;}EntryOfVLArray<T>* p = m_e.m_prev;for( uint n = m_size - 1 ; n > i ; n-- ){p = p->m_prev;}return p->m_t;}template <typename T>VLArray<T> VLArray<T>::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<T> b{};const_iterator itr = begin();for( int m = 1 ; m <= M ; m++ ){b.push_back( *itr );itr++;}return b;}template <typename T>VLArray<T> VLArray<T>::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<T> b{};const_iterator itr = end();for( int m = 1 ; m <= M ; m++ ){itr--;b.push_front( *itr );}return b;}template <typename T>bool VLArray<T>::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 <typename T>bool VLArray<T>::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 <typename T>string VLArray<T>::Display() const{string s = "(";EntryOfVLArray<T>* 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 <typename T> template <typename... Args> inline void VLArray<T>::ExpandParameterPack( const Args&... ) noexcept {};template <typename T>bool operator==( const VLArray<T>& a1 , const VLArray<T>& 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 <typename T> inline bool operator!=( const VLArray<T>& a1 , const VLArray<T>& a2 ) { return !( a1 == a2 ); }template <typename T> VLArray<T> to_VLArray( const uint& N , const T& t ){auto a = VLArray<T>();for( uint n = 0 ; n < N ; n++ ){a.push_back( t );}return a;}template <typename T> inline VLMatrix<1,T> to_VLMatrix( const uint& N , const T& t ){ return to_VLArray( N , t ); }template <typename T> inline VLMatrix<2,T> to_VLMatrix( const uint& N0 , const uint& N1 , const T& t ){ return to_VLArray( N1 , to_VLArray( N0 , t )); }template <typename T> 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 <typename T , typename... Arg>VLArray<T> Frown( const Arg&... args ){VLArray<T> a{};a.Concatenate( args... );return a;}template <typename T> T Sum( const VLArray<T>& a ){T t{};for( auto itr = a.begin() , end = a.end() ; itr != end ; itr++ ){t += *itr;}return t;}template <typename T>void Sort( VLArray<T>& a , const string& method = "normal" , const VLArray<int>& option = VLArray<int>() );template <typename T>void NormalSort( VLArray<T>& a , const VLArray<int>& option = VLArray<int>() );template <typename T>void NormalSortNoCut( VLArray<T>& a );template <typename T>void NormalSortCut( VLArray<T>& a , const uint& cut_length , const bool& cut_large );template <typename T>void MergeSort( VLArray<T>& a , const VLArray<int>& option = VLArray<int>() );template <typename T>void MergeSortNoCut( VLArray<T>& a );template <typename T>void MergeSortCut( VLArray<T>& a , const uint& cut_length , const bool& cut_large , const uint& normal_method_length = 2 );template <typename T>void Sort( VLArray<T>& a , const string& method , const VLArray<int>& option ){if( method == "merge" ){MergeSort( a , option );} else {NormalSort( a , option );}return;}template <typename T>void NormalSort( VLArray<T>& a , const VLArray<int>& option ){if( ! option.empty() ){const uint& cut_length_signed = option[0];if( cut_length_signed != 0 ){if( cut_length_signed > 0 ){NormalSortCut<T>( a , (uint)cut_length_signed , true );} else {NormalSortCut<T>( a , (uint)( - cut_length_signed ) , false );}return;}}NormalSortNoCut<T>( a );return;}template <typename T>void NormalSortNoCut( VLArray<T>& 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 <typename T>void NormalSortCut( VLArray<T>& a , const uint& cut_length , const bool& cut_large ){using type = typename VLArray<T>::iterator;using incr_type = void( type::* )( int );using ins_type = void( VLArray<T>::* )( const type& , const T& );using er_type = type( VLArray<T>::* )( 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<T>::insert_back;er = &VLArray<T>::erase_back;} else {itr0--;incr = &type::operator--;decr = &type::operator++;ins = &VLArray<T>::insert_front;er = &VLArray<T>::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 <typename T>void MergeSort( VLArray<T>& a , const VLArray<int>& 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<T>( a , cut_length , cut_large , (uint)( normal_method_length ) );return;}}MergeSortCut<T>( a , cut_length , cut_large );return;}}MergeSortNoCut<T>( a );return;}template <typename T>void MergeSortNoCut( VLArray<T>& 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<T> b{};for( uint i = 0 ; i < half_size_a ; i++ ){b.push_back( *itr );a.erase( itr );}MergeSortNoCut<T>( a );MergeSortNoCut<T>( 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 <typename T>void MergeSortCut( VLArray<T>& 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<T>( a );} else {NormalSortCut<T>( a , cut_length , cut_large );}return;}const uint half_size_a = size_a / 2;using type = typename VLArray<T>::iterator;type itr = a.begin();VLArray<T> b{};for( uint i = 0 ; i < half_size_a ; i++ ){b.push_back( *itr );a.erase( itr );}MergeSortCut<T>( a , cut_length , cut_large , normal_method_length );MergeSortCut<T>( 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<T>::* )() const;using ins_type = void( VLArray<T>::* )( const type& , const T& );using push_type = void( VLArray<T>::* )( const T& );using pop_type = void( VLArray<T>::* )();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<T>::front;incr = &type::operator++;ins = &VLArray<T>::insert_front;push = &VLArray<T>::push_back;pop_fr = &VLArray<T>::pop_front;pop_ba = &VLArray<T>::pop_back;} else {itr = end;itr--;fr = &VLArray<T>::back;incr = &type::operator--;ins = &VLArray<T>::insert_back;push = &VLArray<T>::push_front;pop_fr = &VLArray<T>::pop_back;pop_ba = &VLArray<T>::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 a;VLArray<ll> A{};for( ll i = 0 ; i < N ; i++ ){cin >> a;A.push_back( a );}Sort( A , "merge" );double answer;if( N % 2 == 0 ){answer = ( A[ N / 2 - 1] + A[ N / 2 ] ) / 2.0;} else {answer = A[ N / 2 ];}cout << answer << endl;return 0;}