#include using namespace std; using Int = long long; template void chmin(T &a,T b){if(a>b) a=b;} template void chmax(T &a,T b){if(a>n; vector a(n); for(Int i=0;i>a[i]; vector< vector > dp(2,vector(n+1,0)); auto check=[&](Int i,Int x){ chmin(dp[0][i+1],x); chmax(dp[1][i+1],x); }; for(Int i=0;i