# CFR 794 E. Choosing Carrot ( Game, Ad hoc )

Problem - 794E - Codeforces

N ≤ 3e5
1 ≤ A[ i ] ≤ 1e9

__若 n 是 1：自明
__若 n 是奇數，那麼答案是 min( A[ n + 1 >> 1 ], max( A[ n - 1 >> 1 ], A[ n + 3 >> 1 ] ) )
__若 n 是偶數，那麼答案是 max( A[ n >> 1 ], A[ n + 2 >> 1 ] )

O( N )

```#include <bits/stdc++.h>
using namespace std;

const int MAXN = int( 3e5 );

int N;
int _A[ MAXN + 2 ], *A = &_A[ 1 ];

int ans[ MAXN ];

signed main() {
ios::sync_with_stdio( 0 );
cin >> N;
for( int i = 0; i < N; ++i ) {
cin >> A[ i ];
}
for( int i = N - ( N & 1 ), best = 0, lp = N / 2 - 1, rp = ( N + 1 ) / 2; i >= 1; i -= 2, --lp, ++rp ) { // how many left
best = max( { best, max( A[ lp ], A[ lp + 1 ] ), max( A[ rp - 1 ], A[ rp ] ) } );
ans[ N - i ] = best;
}
for( int i = N - ( ~N & 1 ), best = 0, lp = ( N - 1 ) / 2, rp = N / 2; i >= 1; i -= 2, --lp, ++rp ) {
best = max( { best, min( A[ lp ], max( A[ lp - 1 ], A[ lp + 1 ] ) ),
min( A[ rp ], max( A[ rp - 1 ], A[ rp + 1 ] ) ) } );
ans[ N - i ] = best;
}
for( int i = 0; i < N; ++i ) {
ans[ N - 1 ] = max( ans[ N - 1 ], A[ i ] );
}
for( int i = 0; i < N; ++i ) {
cout << ans[ i ] << " \n"[ i + 1 == N ];
}
return 0;
}
```