#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)); const Int INF = 1e17; fill(dp[0].begin(),dp[0].end(),INF); fill(dp[1].begin(),dp[1].end(),-INF); dp[0][1]=dp[1][1]=a[0]; auto check=[&](Int i,Int x){ chmin(dp[0][i+1],x); chmax(dp[1][i+1],x); }; for(Int i=1;i