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;
  inline int read() {
    int x = 0, w = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
      w |= ch == '-';
      ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
      x = (x << 3) + (x << 1) + ch - '0';
      ch = getchar();
    }
    return w ? -x : x;
  }
  int T, n, p[1000005], ans[1000005];
  int st[1000005][25], LOG[(1 << 22)];
  inline int pushup(int x, int y) { return p[x] > p[y] ? x : y; }
  inline int que(int l, int r) {
    return pushup(st[l][LOG[r - l + 1]],
                  st[r - (1 << LOG[r - l + 1]) + 1][LOG[r - l + 1]]);
  }
  inline int check(int l, int r, int x, int tp) {
    if (l > r) return 1;
    int res = 1;
    if (tp == 0) {
      int ok = x < -p[l];
      for (int i = l; i < r; i++) ok &= (-p[i] < -p[i + 1]);
      if (ok) {
        for (int i = l; i <= r; i++) ans[i] = -p[i];
        return 1;
      }
      ans[r] = p[r];
      for (int i = r - 1; i >= l; i--) {
        if (p[i] < ans[i + 1]) {
          ans[i] = p[i];
        } else
          ans[i] = -p[i];
        res &= (ans[i] < ans[i + 1]);
      }
      res &= (x < ans[l]);
    } else {
      int ok = p[r] < x;
      for (int i = l; i < r; i++) ok &= (p[i] < p[i + 1]);
      if (ok) {
        for (int i = l; i <= r; i++) ans[i] = p[i];
        return 1;
      }
      ans[l] = -p[l];
      for (int i = l + 1; i <= r; i++) {
        if (-p[i] > ans[i - 1]) {
          ans[i] = -p[i];
        } else
          ans[i] = p[i];
        res &= (ans[i] > ans[i - 1]);
      }
      res &= (x > ans[r]);
    }
    return res;
  }
  int fl = 1;
  void work(int l, int r, int a, int b) {
    if (l > r) return;
    if (l == r) {
      if (a < p[l] || p[l] < b) {
        ans[l] = p[l];
        return;
      } else {
        ans[l] = -p[l];
        fl &= (a < ans[l] || ans[l] < b);
      }
      return;
    }
    int pos = que(l, r);
    if (pos == l) {
      if (a < -p[pos] || -p[pos] < b) {
        ans[pos] = -p[pos];
      } else {
        ans[pos] = p[pos];
        fl &= ((a < p[pos]) || (p[pos] < b));
      }
      work(l + 1, r, max(a, ans[pos]), b);
      return;
    }
    if (pos == r) {
      if (a < p[pos] || p[pos] < b) {
        ans[pos] = p[pos];
      } else {
        ans[pos] = -p[pos];
        fl &= ((a < -p[pos]) || (-p[pos] < b));
      }
      work(l, r - 1, a, min(b, ans[pos]));
      return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) {
      if (check(l, pos - 1, a, 0) && -p[pos] < b) {
        ans[pos] = -p[pos];
        work(pos + 1, r, max(a, ans[pos - 1]), b);
      } else {
        ans[pos] = p[pos];
        fl &= check(pos + 1, r, b, 1);
        fl &= (p[pos] > a);
        work(l, pos - 1, a, min(b, ans[pos + 1]));
      }
    } else {
      if (check(pos + 1, r, b, 1) && p[pos] > a) {
        ans[pos] = p[pos];
        work(l, pos - 1, a, min(b, ans[pos + 1]));
      } else {
        ans[pos] = -p[pos];
        fl &= check(l, pos - 1, a, 0);
        fl &= (-p[pos] < b);
        work(pos + 1, r, max(a, ans[pos - 1]), b);
      }
    }
  }
  void solve() {
    fl = 1;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) p[i] = read();
    for (int i = n; i >= 1; i--) {
      st[i][0] = i;
      for (int j = 1; j <= 20; j++) {
        if (i + (1 << j) - 1 > n) continue;
        st[i][j] = pushup(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
      }
    }
    work(1, n, -n - 1, n + 1);
    if (!fl)
      printf("NO\n");
    else {
      printf("YES\n");
      for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
      printf("\n");
    }
  }
  int main() {
    for (int i = 0; i <= 20; i++) {
      for (int j = (1 << i); j < (1 << (i + 1)); j++) LOG[j] = i;
    }
    scanf("%d", &T);
    while (T--) solve();
    return 0;
  }
  