#include #define REP(i,n) for(int i=0,i##_len=(n);i=0;--i) #define rep(i,a,b) for(int i=int(a);i=int(b);--i) #define All(x) (x).begin(),(x).end() #define rAll(x) (x).rbegin(),(x).rend() #define ITR(i,x) for(auto i=(x).begin();i!=(x).end();++i) using namespace std; using Graph = vector>; typedef long long ll; typedef pair P; typedef vector vi; typedef vector vvi; typedef vector vl; typedef vector vvl; constexpr ll mod = 1e9+7; constexpr double eps = 1e-9; const double PI = acos(-1); void solve(); P bisearch(ll l,ll r,function f){ while((l+1)n/x;}).first;} ll roundup(ll n,ll div){ if(n>0) return (n-1)/div+1; else return n/div; } bool square(ll a){ll n=SQRT(a);return a==n*n;} ll npow(ll x, ll n){ ll ans = 1; while(n != 0){ if(n&1) ans = ans*x; x = x*x; n = n >> 1; } return ans; } ll mpow(ll x, ll n){ //x^n(mod) ←普通にpow(x,n)では溢れてしまうため,随時mod計算 2分累乗法だから早い ll ans = 1; while(n != 0){ if(n&1) ans = ans*x % mod; x = x*x % mod; n = n >> 1; } return ans; } ll inv_mod(ll a){return mpow(a,mod-2);} int digitsum(ll N,int a){ if(N==0) return 0; int ret=0; ret+=digitsum(N/a,a)+N%a; return ret; } ll gcd(ll x,ll y){return y ? gcd(y,x%y) : x;};//xとyの最大公約数 ll lcm(ll x,ll y){return x/gcd(x,y)*y;}//xとyの最小公倍数 void YN(bool flg){std::cout<<(flg?"YES":"NO")< LEFT,RIGHT; function F; int N; public: Ruiseki(ll INI,const vector &a,function f){ N=a.size();F=f; LEFT.resize(N+1);RIGHT.resize(N+1); LEFT[0]=RIGHT[0]=INI; REP(i,N){ LEFT[i+1]=F(LEFT[i],a[i]); RIGHT[i+1]=F(RIGHT[i],a[N-i-1]); } } ll out(int l,int r){//[l,r)の外の累積 return F(LEFT[l],RIGHT[N-r]); } }; class mint { private: ll _num,_mod; mint set(ll num){ _num = num ; if(_num>=0) _num%=_mod; else _num+=(1-(_num+1)/_mod)*_mod; return *this; } ll _mpow(ll x, ll n){ //x^n(mod) ←普通にpow(x,n)では溢れてしまうため,随時mod計算 2分累乗法だから早い ll ans = 1; while(n != 0){ if(n&1) ans = ans*x % _mod; x = x*x % _mod; n = n >> 1; } return ans; } ll imod(ll n){return _mpow(n , _mod-2);} public: mint(){ _num = 0;_mod=mod; } mint(ll num){ _mod = mod; _num = (num+(1LL<<25)*mod) % mod; } mint(ll num,ll M){ _mod=M;_num=(num+(1LL<<25)*mod)%_mod; } mint(const mint &cp){_num=cp._num;_mod=cp._mod;} mint operator= (const ll x){ return set(x); } mint operator+ (const ll x){ return mint(_num + (x % _mod) , _mod); } mint operator- (const ll x){ return mint(_num - (x % _mod), _mod); } mint operator* (const ll x){ return mint(_num * (x % _mod) , _mod); } mint operator/ (ll x){ return mint(_num * imod(x) , _mod);} mint operator+=(const ll x){ return set(_num + (x % _mod)); } mint operator-=(const ll x){ return set(_num - (x % _mod)); } mint operator*=(const ll x){ return set(_num * (x % _mod)); } mint operator/=(ll x){ return set(_num * imod(x));} mint operator+ (const mint &x){ return mint(_num + x._num , _mod); } mint operator- (const mint &x){ return mint(_num - x._num , _mod);} mint operator* (const mint &x){ return mint(_num * x._num , _mod); } mint operator/ (mint x){ return mint(_num * imod(x._num) , _mod);} mint operator+=(const mint &x){ return set(_num + x._num); } mint operator-=(const mint &x){ return set(_num - x._num); } mint operator*=(const mint &x){ return set(_num * x._num); } mint operator/=(mint x){ return set(_num * imod(x._num));} bool operator<(const mint &x)const{return _num(const mint &x)const{return _num>x._num;} friend mint operator+(ll x,const mint &m){return mint(m._num + (x % m._mod) , m._mod);} friend mint operator-(ll x,const mint &m){return mint( (x % m._mod) - m._num , m._mod);} friend mint operator*(ll x,const mint &m){return mint(m._num * (x % m._mod) , m._mod);} friend mint operator/(ll x,mint m){return mint(m.imod(m._num) * x , m._mod);} explicit operator ll() { return _num; } explicit operator int() { return (int)_num; } friend ostream& operator<<(ostream &os, const mint &x){ os << x._num; return os; } friend istream& operator>>(istream &is, mint &x){ll val; is>>val; x.set(val); return is;} }; template class MAT{ private: int row,col; vector> _A; MAT set(vector> A){_A = A ; return *this;} public: MAT(){ } MAT(int n,int m){ if(n<1 || m<0){cout << "err Matrix::Matrix" < a(col,0.0); _A.push_back(a); } // 値の初期化 if(m==0) REP(i,n) _A[i][i]=1.0; } MAT(const MAT &cp){_A=cp._A;row=cp.row;col=cp.col;} T* operator[] (int i){return _A[i].data();} MAT operator= (vector> x) {return set(x);} MAT operator+ (MAT x) { if(row!=x.row || col!=x.col){ cout << "err Matrix::operator+" <>=1; } return r; } MAT operator+= (MAT x) { if(row!=x.row || col!=x.col){ cout << "err Matrix::operator+=" <>(){return _A;} friend ostream &operator<<(ostream &os,const MAT &x){ REP(i,x.row) REP(j,x.col) os<>(istream &is,MAT &x){REP(i,x.row) REP(j,x.col) is>>x._A[i][j];return is;} int size_row(){return row;} int size_col(){return col;} MAT transpose(){ MAT r(col,row); REP(i,col) REP(j,row) r[i][j]=_A[j][i]; return r; } MAT inverse(){ T buf; MAT inv_a(row,0); vector> a=_A; //掃き出し法 REP(i,row){ buf=1/a[i][i]; REP(j,row){ a[i][j]*=buf; inv_a[i][j]*=buf; } REP(j,row){ if(i!=j){ buf=a[j][i]; REP(k,row){ a[j][k]-=a[i][k]*buf; inv_a[j][k]-=inv_a[i][k]*buf; } } } } return inv_a; } // O( n^3 ). int rank() { vector> A=_A; const int n = row, m = col; int r = 0; for(int i = 0; r < n && i < m; ++i) { int pivot = r; for(int j = r+1; j < n; ++j) if(fabs(A[j][i]) > fabs(A[pivot][i])) pivot = j; swap(A[pivot], A[r]); if(fabs(A[r][i]) < eps) continue; for (int k = m-1; k >= i; --k) A[r][k] /= A[r][i]; rep(j,r+1,n) rep(k,i,m) A[j][k] -= A[r][k] * A[j][i]; ++r; } return r; } }; class UnionFind{//UnionFind木 private: vector Parent,es; vector diff_weight; public: UnionFind(int N){ es.resize(N,0); Parent.resize(N,-1); diff_weight.resize(N,0LL); } int root(int A){ if(Parent[A]<0) return A; else{ int r = root(Parent[A]); diff_weight[A] += diff_weight[Parent[A]]; // 累積和をとる return Parent[A]=r; } } bool issame(int A,int B){ return root(A)==root(B); } ll weight(int x) { root(x); // 経路圧縮 return diff_weight[x]; } ll diff(int x, int y) { return weight(y) - weight(x); } int size(int A){ return -Parent[root(A)]; } int eize(int A){ return es[root(A)]; } bool connect(int A,int B){ A=root(A); B=root(B); if(A==B) return false; if(size(A) fac; vector ifac; public: Factorial(ll N){ fac.push_back(1); REP(i,N) fac.push_back(fac[i]*(i+1)%mod); ifac.resize(N+1); ifac[N]=inv_mod(fac[N]); REP(i,N) ifac[N-1-i]=(ifac[N-i]*(N-i))%mod; } ll fact(ll a){return fac[a];} ll ifact(ll a){return ifac[a];} ll cmb(ll a,ll b){ if(a==0&&b==0) return 1; if(a Prime_Number; vector isp; public: SOSU(int N){ isp.resize(N+1,true); isp[0]=isp[1]=false; rep(i,2,N+1) if(isp[i]){ Prime_Number.push_back(i); for(int j=2*i;j<=N;j+=i) isp[j]=false; } } int operator[](int i){return Prime_Number[i];} int size(){return Prime_Number.size();} int back(){return Prime_Number.back();} bool isPrime(int q){return isp[q];} }; class Divisor{//素因数分解をしてから約数列挙、分解結果はP(底,指数)でpfacにまとめている private: vector F; vector

pfactorize; public: Divisor(ll N){ for(ll i = 1; i * i <= N; i++) { if(N % i == 0) { F.push_back(i); if(i * i != N) F.push_back(N / i); } } sort(begin(F), end(F)); SOSU p(SQRT(N)+1); REP(i,p.size()){ pfactorize.push_back(P(p[i],0)); while(N%p[i]==0){ N/=p[i]; pfactorize.back().second++; } if(pfactorize.size()==0) pfactorize.pop_back(); } if(N>1) pfactorize.push_back(P(N,1)); } int size(){return F.size();} vector

pfac(){return pfactorize;} ll operator[](int k){return F[k];} }; struct Solutions{ ll napsack(int kinds,int MAX_W,const vl &weight,const vl &cost){ vector> dp(kinds+1,vector(MAX_W+1,0)); REP(i,kinds) REP(j,MAX_W+1){ if(j> dp(kinds+1,vector(MAX_W+1,0)); REP(i,kinds) REP(j,MAX_W+1){ if(j ps(1<<(kinds/2)); REP(i,1<>j&1){ sw += weight[j]; sv += cost[j]; } } ps[i] = P(sw,sv); } sort(ps.begin(),ps.begin() + (1<>j)&1){ sw += weight[n2+j]; sv += cost[n2+j]; } } if(sw<=MAX_W){ ll tv = (lower_bound(ps.begin(),ps.begin()+m,P(MAX_W-sw,LLONG_MAX))-1)->second; res = max(res,sv+tv); } } return res; } ll choose_MonN(int N,int M,const vl &cost){ vvl dp(N+1,vl(M+1,-1LL<<58)); REP(i,N+1) dp[i][0]=0; REP(i,N) REP(j,M){ if(j>i) break; dp[i+1][j+1]=max(dp[i][j+1],dp[i][j]+cost[i]); } return dp[N][M]; } ll Partition_Func(int n,int k){ vector> dp(k+1,vector (n+1,0)); dp[0][0]=1; rep(i,1,k+1) REP(j,n+1){ if(j-i>=0) dp[i][j]=(dp[i][j-i]+dp[i-1][j]); else dp[i][j]=dp[i-1][j]; } return dp[k][n]; } int LCS(string s,string t){ int n=s.length(),m=s.length(); vector> dp(n+1,vector(m+1)); REP(i,n) REP(j,m){ if (s[i] == t[j]) dp[i+1][j+1] = dp[i][j] + 1; else dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]); } return dp[n][m]; } int LIS(const vector a){ int n=a.size(); ll INF=1LL<<50; vector dp(n+1,INF); REP(i,n) *lower_bound(All(dp),a[i])=a[i]; int k=lower_bound(All(dp),INF)-dp.begin(); return k; } int max_flow(int s,int t,const vector> &g){ struct edge_{int to,cap, rev;}; vector used(g.size(),false); vector> G(g.size()); REP(i,g.size()) REP(j,g[i].size()){ int from = i, to = g[i][j].second; int cap = g[i][j].first; G[from].push_back((edge_){to,cap,(int)G[to].size()}); G[to].push_back((edge_){from,0,(int)G[from].size()-1}); } auto dfs = [&](auto&& f,int v,int t,int fl)->int{ if(v==t) return fl; used[v] = true; REP(i,G[v].size()){ edge_ &e = G[v][i]; if(!used[e.to] && e.cap>0){ int d = f(f, e.to,t,min(fl,e.cap)); if(d>0){ e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; }; int flow=0; while(1){ used.assign(used.size(),false); int f = dfs(dfs,s,t,INT_MAX); if(f==0) return flow; flow += f; } } int bipartite_matching_calculate(const Graph &g){ int V = g.size(); vi match(V,-1); vector used(V,false); auto dfs = [&](auto&& f,int v)->bool{ used[v]=true; REP(i,g[v].size()){ int u = g[v][i], w = match[u]; if(w<0 || !used[w] && f(f,w)){ match[v]=u; match[u]=v; return true; } } return false; }; int res=0; REP(v,V){ if(match[v] < 0){ used.assign(V,false); if(dfs(dfs,v)) res++; } } return res; } int bipartite_matching(int l,int r,function F){ int V = l+r; Graph G(V); REP(i,l) REP(j,r) if(F(i,j)){ G[i].push_back(l+j); G[l+j].push_back(i); } return bipartite_matching_calculate(G); } }; struct compress{ map zip; vector unzip; compress(vector x){ unzip=x; sort(All(x)); x.erase(unique(All(x)),x.end()); REP(i,x.size()){ zip[x[i]]=i; } } int operator[](int k){return zip[unzip[k]];} }; struct edge{ int from;int to;ll cost; void push(int a,int b,int c){ from=a;to=b;cost=c; } bool operator<(const edge& y) const{ if(cost!=y.cost) return cost(const edge& y) const{ if(cost!=y.cost) return cost>y.cost; else if(to!=y.to) return to>y.to; else return from>y.from;} bool operator==(const edge& y) const{return *this==y;} }; class lca { public: const int n = 0; const int log2_n = 0; std::vector> parent; std::vector depth; lca() {} lca(const Graph &g, int root) : n(g.size()), log2_n(log2(n) + 1), parent(log2_n, std::vector(n)), depth(n) { dfs(g, root, -1, 0); for (int k = 0; k + 1 < log2_n; k++) { for (int v = 0; v < (int)g.size(); v++) { if (parent[k][v] < 0) parent[k + 1][v] = -1; else parent[k + 1][v] = parent[k][parent[k][v]]; } } } void dfs(const Graph &g, int v, int p, int d) { parent[0][v] = p; depth[v] = d; REP(j,g[v].size()) { if (g[v][j] != p) dfs(g, g[v][j], v, d + 1); } } int get(int u, int v) { if (depth[u] > depth[v]) std::swap(u, v); for (int k = 0; k < log2_n; k++) { if ((depth[v] - depth[u]) >> k & 1) { v = parent[k][v]; } } if (u == v) return u; for (int k = log2_n - 1; k >= 0; k--) { if (parent[k][u] != parent[k][v]) { u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } }; template //SegmentTree((要素数) int n_,(演算) F f,(更新) G g,(初期値) T d1) struct SegmentTree{ typedef function F; typedef function G; int n; F f; G g; T d1; E d0; vector dat; SegmentTree(){}; SegmentTree(int n_,F f,G g,T d1, vector v=vector()): f(f),g(g),d1(d1){ init(n_); if(n_==(int)v.size()) build(n_,v); } void init(int n_){ n=1; while(n v){ for(int i=0;i=0;i--) dat[i]=f(dat[i*2+1],dat[i*2+2]); } void update(int k,E a){ k+=n-1; dat[k]=g(dat[k],a); while(k>0){ k=(k-1)/2; dat[k]=f(dat[k*2+1],dat[k*2+2]); } } inline T query(int a,int b){ T vl=d1,vr=d1; for(int l=a+n,r=b+n;l>=1,r>>=1) { if(l&1) vl=f(vl,dat[(l++)-1]); if(r&1) vr=f(dat[(--r)-1],vr); } return f(vl,vr); } }; struct GP{ double x,y; GP(double X=0,double Y=0):x(X),y(Y){} GP(const GP &cp){ x=cp.x;y=cp.y; } GP& set(double X,double Y){ x=X;y=Y; return *this; } GP& operator=(const GP &p){return set(p.x , p.y);} GP operator+(const GP &p)const{return GP(x+p.x , y+p.y);} GP operator-(const GP &p)const{return GP(x-p.x , y-p.y);} GP operator*(double s)const{return GP(x*s,y*s);} GP operator/(double s)const{return GP(x/s,y/s);} friend GP operator*(double s,const GP &r){return GP(r.x*s,r.y*s);} friend GP operator/(double s,const GP &r){return GP(r.x/s,r.y/s);} double operator*(GP p)const{return dot(p);} double operator^(GP p)const{return cross(p);} GP& operator+=(const GP &p){return set(x+p.x , y+p.y);} GP& operator-=(const GP &p){return set(x-p.x , y-p.y);} GP& operator*=(double s){return set(x*s,y*s);} GP& operator/=(double s){return set(x/s,y/s);} double dot(const GP &p)const{return x*p.x + y*p.y;} double cross(const GP &p)const{return x*p.y-p.x*y;} int ort()const{ if(fabs(x)0) return (x>0)?1:2; else return (x<=0)?3:4; } bool operator<(const GP &p)const{ int o=ort(),po=p.ort(); if(o!=po) return o0; } } friend istream& operator>>(istream &is, GP &x){double valX,valY; is>>valX>>valY; x.set(valX,valY); return is;} friend ostream& operator<<(ostream &os, const GP &v){ os << v.x<<" "<0) return PI/2.0; if(y==0) return -1.0; if(y<0) return -PI/2.0; }else{ if(y==0){ if(x<0) return PI; if(x>0) return 0.0; } else return atan2(y,x); } } void rotate(double theta){ double X=x,Y=y; x=cos(theta)*X-sin(theta)*Y; y=sin(theta)*X+cos(theta)*Y; } }; struct Line{ GP A,B; Line(GP p1=GP(0,0),GP p2=GP(1,1)):A(p1),B(p2){} double len()const{return (B-A).norm();} GP shortest_point(const GP &x)const{ double a=B.x-A.x,b=B.y-A.y; double t=-(a*(A.x-x.x)+b*(A.y-x.y))/(a*a+b*b); return GP(a*t+A.x,b*t+A.y); } double dist(const GP &x)const{ return (x-shortest_point(x)).norm(); } bool online(const GP &x)const{ return ((B-A)^(x-A))==0&&(x-A).norm()<=len()&&(x-B).norm()<=len(); } friend istream& operator>>(istream &is, Line &x){GP X,Y; is>>X>>Y;x.A=X;x.B=Y;return is;} friend ostream& operator<<(ostream &os, const Line &x){ os << x.A << x.B; return os; } }; struct Triangle{ GP a,b,c; Triangle(GP p1=GP(0,0),GP p2=GP(1,0),GP p3=(0,1)):a(p1),b(p2),c(p3){} double A()const{double res=fabs((b-a).rad()-(c-a).rad());if(res>=PI) res-=PI;return res;} double B()const{double res=fabs((a-b).rad()-(c-b).rad());if(res>=PI) res-=PI;return res;} double C()const{double res=fabs((a-c).rad()-(b-c).rad());if(res>=PI) res-=PI;return res;} Line AB()const{return Line(a,b);} Line BC()const{return Line(b,c);} Line CA()const{return Line(c,a);} GP G()const{return (a+b+c)/3;} GP O()const{return (sin(2*A())*a+sin(2*B())*b+sin(2*C())*c)/(sin(2*A())+sin(2*B())+sin(2*C()));} double R()const{return a.norm()/(2*sin(A()));} GP I()const{return (a.norm()*a+b.norm()*b+c.norm()*c)/(a.norm()+b.norm()+c.norm());} double r()const{return 2*area()/((a-b).norm()+(b-c).norm()+(c-a).norm());} GP H()const{return (tan(A())*a+tan(B())*b+tan(C())*c)/(tan(A())+tan(B())+tan(C()));} double AH()const{return 2*R()*cos(A());} double BH()const{return 2*R()*cos(B());} double CH()const{return 2*R()*cos(C());} double area()const{return ((b-a)^(c-a))/2;} bool inside(const GP &x)const{ return ((b-a)^(x-a))*((c-a)^(x-a))<0&& ((a-b)^(x-b))*((c-b)^(x-b))<0&& ((a-c)^(x-c))*((b-c)^(x-c))<0; } bool online(const GP &x)const{return AB().online(x)||BC().online(x)||CA().online(x);} bool outside(const GP &x)const{return (!inside(x)&&!online(x));} friend istream& operator>>(istream &is, Triangle &x){GP X,Y,Z; is>>X>>Y>>Z; x.a=X;x.b=Y;x.c=Z;return is;} friend ostream& operator<<(ostream &os, const Triangle &v){ os << v.a << v.b; return os; } }; struct rational{ ll a,b; rational(ll A=1,ll B=1):a(A),b(B){ ll g=gcd(llabs(a),llabs(b)); a/=g;b/=g; }; rational operator+(const rational &r)const{return rational(a*r.b+b*r.a,b*r.b);} rational operator-(const rational &r)const{return rational(a*r.b-b*r.a,b*r.b);} rational operator*(const rational &r)const{return rational(a*r.a,b*r.b);} rational operator/(const rational &r)const{return rational(a*r.b,b*r.a);} rational& set(ll A,ll B){ll g=gcd(llabs(A),llabs(B));a=A/g;b=B/g;return *this;} rational& operator+=(const rational &r){return set(a*r.b+b*r.a,b*r.b);} rational& operator-=(const rational &r){return set(a*r.b-b*r.a,b*r.b);} rational& operator*=(const rational &r){return set(a*r.a,b*r.b);} rational& operator/=(const rational &r){return set(a*r.b,b*r.a);} bool operator<(const rational &r)const{ if(b*r.b>=0) return a*r.bb*r.a; } bool operator==(const rational &r)const{return a*r.b==b*r.a;} bool operator>(const rational &r)const{ if(b*r.b>=0) return a*r.b>b*r.a; else return a*r.b>(istream &is, rational &x){ll vala,valb; is>>vala>>valb; x.set(vala,valb); return is;} }; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); solve(); return 0; } void solve(){ int N;cin>>N; vector ans(N); REP(i,N) cin>>ans[i]; sort(rAll(ans)); REP(i,N) cout<