description: You are given a permutation p consisting of n integers 1, 2, ..., n (a permutation is an array where each element from 1 to n occurs exactly once).
  
  Let's call an array a bipartite if the following undirected graph is bipartite:
  
    * the graph consists of n vertices; 
    * two vertices i and j are connected by an edge if i < j and a_i > a_j. 
  
  
  
  Your task is to find a bipartite array of integers a of size n, such that a_i = p_i or a_i = -p_i, or report that no such array exists. If there are multiple answers, print any of them.
  
  Input
  
  The first line contains a single integer t (1 ≤ t ≤ 2 ⋅ 10^5) — the number of test cases.
  
  The first line of each test case contains a single integer n (1 ≤ n ≤ 10^6) — the size of the permutation.
  
  The second line contains n integers p_1, p_2, ..., p_n.
  
  The sum of n over all test cases doesn't exceed 10^6.
  
  Output
  
  For each test case, print the answer in the following format. If such an array a does not exist, print "NO" in a single line. Otherwise, print "YES" in the first line and n integers — array a in the second line.
  
  Example
  
  Input
  
  
  4
  3
  1 2 3
  6
  1 3 2 6 5 4
  4
  4 1 3 2
  8
  3 2 1 6 7 8 5 4
  
  
  Output
  
  
  YES
  1 2 3
  NO
  YES
  -4 -1 -3 -2
  YES
  -3 -2 1 6 7 -8 -5 -4
solution: #include <bits/stdc++.h>
  using namespace std;
  using ll = long long;
  void solve() {
    int n;
    cin >> n;
    vector<int> vals(n);
    for (int& v : vals) cin >> v;
    vector<int> dp(2 * n, n + 1), pre(2 * n, -1);
    dp[0] = -n;
    dp[1] = -n;
    for (int i = 1; i < n; ++i) {
      int ind = 2 * i;
      for (int x = 0; x <= 1; ++x) {
        int vi = vals[i] * (2 * x - 1);
        for (int y = 0; y <= 1; ++y) {
          int vj = vals[i - 1] * (2 * y - 1);
          pair<int, int> pr = {dp[ind - 2 + y], vj};
          for (int s = 0; s <= 1; ++s, swap(pr.first, pr.second)) {
            if (pr.first <= vi && pr.second < dp[ind + x]) {
              dp[ind + x] = pr.second;
              pre[ind + x] = ind - 2 + y;
            }
          }
        }
      }
    }
    if (dp[2 * n - 1] <= n) {
      cout << "YES\n";
      int ind = 2 * n - 1;
      for (int i = n - 1; i >= 0; --i) {
        if ((ind % 2) == 0) vals[i] *= -1;
        ind = pre[ind];
      }
      for (int v : vals) cout << v << ' ';
      cout << '\n';
    } else {
      cout << "NO\n";
    }
  }
  int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    for (int ti = 0; ti < t; ++ti) solve();
  }
  