感觉是个垃圾题啊， 为什么过的人这么少。。

dp[ i ][ 0 ]表示处理完前 i 个， 第 i 个是递增序列序列里的元素，递减序列的最大值。

dp[ i ][ 1 ]表示处理完前 i 个， 第 i 个是递减序列序列里的元素，递增序列的最小值。

然后随便转移转移顺便记录一下路径就好啦。

#include
     
      #define LL long long#define fi first#define se second#define mk make_pair#define PLL pair
      
       #define PLI pair
       
        #define PII pair
        
         #define SZ(x) ((int)x.size())#define ull unsigned long longusing namespace std;const int N = 2e5 + 7;const int inf = 0x3f3f3f3f;const LL INF = 0x3f3f3f3f3f3f3f3f;const int mod = 1000000007;const double eps = 1e-6;const double PI = acos(-1);int n, a[N], ans[N];int dp[N][2], path[N][2];int main() {    scanf("%d", &n);    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);    for(int i = 1; i <= n; i++)        dp[i][0] = -inf, dp[i][1] = inf;    dp[1][0] = 1e9 + 1;    dp[1][1] = -1;    for(int i = 1; i < n; i++) {        if(dp[i][0] > -inf) {            if(a[i + 1] > a[i]) {                if(dp[i][0] > dp[i + 1][0]) {                    dp[i + 1][0] = dp[i][0];                    path[i + 1][0] = 0;                }            }            if(a[i + 1] < dp[i][0]) {                if(a[i] < dp[i + 1][1]) {                    dp[i + 1][1] = a[i];                    path[i + 1][1] = 0;                }            }        }        if(dp[i][1] < inf) {            if(a[i + 1] < a[i]) {                if(dp[i][1] < dp[i + 1][1]) {                    dp[i + 1][1] = dp[i][1];                    path[i + 1][1] = 1;                }            }            if(a[i + 1] > dp[i][1]) {                if(a[i] > dp[i + 1][0]) {                    dp[i + 1][0] = a[i];                    path[i + 1][0] = 1;                }            }        }    }    if(dp[n][0] > -inf) {        puts("YES");        int now = 0;        for(int i = n; i >= 1; i--) {            ans[i] = now;            now = path[i][now];        }        for(int i = 1; i <= n; i++) printf("%d ", ans[i]);        puts("");    } else if(dp[n][1] < inf) {        puts("YES");        int now = 1;        for(int i = n; i >= 1; i--) {            ans[i] = now;            now = path[i][now];        }        for(int i = 1; i <= n; i++) printf("%d ", ans[i]);        puts("");    } else {        puts("NO");    }    return 0;}/**/