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;
  template <typename T>
  using MinHeap = priority_queue<T, vector<T>, greater<T>>;
  template <typename T>
  using MaxHeap = priority_queue<T>;
  const long double PI = 3.14159265358979323846;
  const long double E = 2.718281828459;
  const long double EPS = 1e-8;
  long long pow2(long long n) { return 1ll << n; }
  mt19937 rng(
      (unsigned int)chrono::steady_clock::now().time_since_epoch().count());
  long long n;
  long long idx(long long x, long long y) { return x * 2 * (n + 1) + y; }
  pair<long long, long long> rev(long long idx) {
    long long x = idx / (2 * n + 2);
    long long y = idx % (2 * n + 2);
    return {x, y};
  }
  int main(int argn, char **argv) {
    ios::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    for (int(I) = (0); (I) <= ((T)-1); (I)++) {
      cin >> n;
      vector<long long> p(n);
      for (int(i) = (0); (i) <= ((n)-1); (i)++) cin >> p[i];
      stack<pair<long long, long long>> st;
      st.emplace(0, 0);
      map<long long, long long> last;
      bool found = true;
      for (int(i) = (0); (i) <= ((n)-1); (i)++) {
        vector<tuple<long long, long long, long long>> vec;
        while (!st.empty()) {
          auto [x, y] = st.top();
          st.pop();
          long long pre = idx(x, y);
          if (x < -p[i] + n + 1)
            vec.emplace_back(-p[i] + n + 1, y, pre);
          else if (x < p[i] + n + 1)
            vec.emplace_back(p[i] + n + 1, y, pre);
          if (y < -p[i] + n + 1)
            vec.emplace_back(x, -p[i] + n + 1, pre);
          else if (y < p[i] + n + 1)
            vec.emplace_back(x, p[i] + n + 1, pre);
        }
        sort((vec).begin(), (vec).end());
        for (auto [x, y, pre] : vec) {
          bool can = true;
          if (!st.empty()) {
            auto [x0, y0] = st.top();
            if (y >= y0) can = false;
          }
          if (can) st.emplace(x, y), last[idx(x, y)] = pre;
        }
        if (st.empty()) {
          found = false;
          break;
        };
      }
      if (found) {
        cout << "YES" << endl;
        vector<long long> sign(n, 1);
        auto [x, y] = st.top();
        long long a = x, b = y;
        long long crt = n - 1;
        while (1) {
          if (a == 0 && b == 0) break;
          ;
          if (a - (n + 1) + p[crt] == 0) sign[crt] = -1;
          if (b - (n + 1) + p[crt] == 0) sign[crt] = -1;
          long long pre = last[idx(a, b)];
          auto [x, y] = rev(pre);
          a = x, b = y, crt--;
        }
        for (int(i) = (0); (i) <= ((n)-1); (i)++) cout << p[i] * sign[i] << " ";
        cout << endl;
      } else
        cout << "NO" << endl;
    }
  }
  