难度：\(2.5/10\)
简单 dp。容易想到设 \(f_{i,0/1}\) 表示当前处理了前 \(i\) 个数：
- \(0\)：当前元素处于递增序列中，递减序列最后一个元素的最大值。
- \(1\)：当前元素处于递减序列中，递增序列最后一个元素的最小值。
转移是容易的，分四类讨论当前元素和上一个元素分别位于递增序列 / 递减序列中即可。总时间复杂度为 \(O(n)\)。
#pragma GCC optimize(3, "Ofast", "inline", "unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define int long longusing namespace std;
const int N = 1000010;
const int mod = 998244353;
const long long inf = 1e18;using ld = long double;
using ull = unsigned long long;
using i128 = __int128;
const ull base = 13331;namespace Luminescent
{const double pi = acos(-1);const ld pi_l = acosl(-1);struct DSU{int fa[N], siz[N];inline DSU() { iota(fa, fa + N, 0), fill(siz, siz + N, 1); }inline void init(int maxn) { iota(fa, fa + maxn + 1, 0), fill(siz, siz + maxn + 1, 1); }inline int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }inline int merge(int x, int y){x = find(x), y = find(y);if (siz[x] > siz[y])x ^= y ^= x ^= y;if (x != y)return fa[x] = y, siz[y] += siz[x], 1;return 0;}};constexpr inline void add(int &x, int a) { x = (x + a) % mod; }constexpr inline void del(int &x, int a) { x = (x - a + mod) % mod; }constexpr inline int power(int a, int b, int c){int res = 1;while (b){if (b & 1)res = 1ll * res * a % c;a = 1ll * a * a % c, b >>= 1;}return res;}constexpr inline int inversion(int x) { return power(x, mod - 2, mod); }constexpr inline int inversion(int x, int Mod) { return power(x, Mod - 2, Mod); }constexpr inline int exgcd(int a, int b, int &x, int &y){if (!b)return x = 1, y = 0, a;int g = exgcd(b, a % b, y, x);y -= a / b * x;return g;}int _exgcd_xp, _exgcd_yp;constexpr inline int exgcd_inv(int a, int Mod){exgcd(a, Mod, _exgcd_xp, _exgcd_yp);return (_exgcd_xp % Mod + Mod) % Mod;}constexpr inline int varphi(int x){int phi = 1;for (int i = 2; i * i <= x; ++i)if (x % i == 0){phi *= (i - 1);x /= i;while (x % i == 0)phi *= i, x /= i;}if (x > 1)phi *= (x - 1);return phi;}
}
using namespace Luminescent;namespace Loyalty
{int a[N];struct BIT{int tree[N];inline BIT() { memset(tree, 0, sizeof tree); }inline void clr(int x) { for (; x < N; x += (x &- x)) tree[x] = 0; }inline void add(int x, int v) { for (; x < N; x += (x &- x)) tree[x] += v; }inline int qry(int x) { int s = 0; for (; x; x -= (x &- x)) s += tree[x]; return s; }inline int qry(int l, int r) { return qry(r) - qry(l - 1); }} fwt;int f[N][2], g[N][2], res[N];// 0: 单调递增序列 递减序列最后一个元素最大值// 1: 单调递减序列 递增序列最后一个元素最小值inline void init() {}inline void main([[maybe_unused]] int _ca, [[maybe_unused]] int _atc){int n;cin >> n;for_each(a + 1, a + n + 1, [&](auto &input) { cin >> input; });f[1][0] = inf, f[1][1] = -inf;if (n == 1){cout << "Yes\n1\n";return;}int low = *min_element(a + 1, a + n + 1), high = *max_element(a + 1, a + n + 1);for (int i = 2; i <= n; ++i){f[i][0] = -inf, f[i][1] = inf;// 1. 当前元素递增 上一个元素递增if (a[i] > a[i - 1])f[i][0] = f[i - 1][0], g[i][0] = 0;// 2. 当前元素递增 上一个元素递减if (a[i] > f[i - 1][1] && f[i][0] < a[i - 1])f[i][0] = a[i - 1], g[i][0] = 1;// 3. 当前元素递减 上一个元素递减if (a[i] < a[i - 1])f[i][1] = f[i - 1][1], g[i][1] = 1;// 4. 当前元素递减 上一个元素递增if (a[i] < f[i - 1][0] && f[i][1] > a[i - 1])f[i][1] = a[i - 1], g[i][1] = 0;}// for (int i = 1; i <= n; ++i)// cerr << "debug: " << f[i][0] << ' ' << f[i][1] << '\n';if (f[n][0] >= low && f[n][0] <= high || f[n][1] >= low && f[n][1] <= high){cout << "YES\n";if (f[n][0] >= low && f[n][0] <= high){int x = n, y = 0;while (x)res[x] = y, y = g[x--][y];}else{int x = n, y = 1;while (x)res[x] = y, y = g[x--][y];}for_each(res + 1, res + n + 1, [&](auto &output) { cout << output << ' '; });cout << '\n';}elsecout << "NO\n";}
}signed main()
{cin.tie(0)->sync_with_stdio(false);cout << fixed << setprecision(15);int T = 1;// cin >> T;Loyalty::init();for (int ca = 1; ca <= T; ++ca)Loyalty::main(ca, T);return 0;
}