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;
  const int Maxn = 1000005;
  const int Inf = 1000000000;
  int T;
  int n;
  int p[Maxn];
  int L[Maxn], R[Maxn];
  int seq[Maxn], slen;
  int root;
  vector<pair<int, int> > fromlef[Maxn], fromrig[Maxn];
  vector<pair<int, int> > mylef[Maxn], myrig[Maxn];
  int res[Maxn];
  vector<pair<int, int> > joinLeft(const vector<pair<int, int> > &A,
                                   const vector<pair<int, int> > &B) {
    vector<pair<int, int> > C;
    for (int i = 0; i < A.size(); i++) {
      int pnt = 0;
      while (pnt < B.size() && A[i].second > B[pnt].first) pnt++;
      int got = pnt < B.size() ? B[pnt].second : Inf;
      C.push_back(pair<int, int>(A[i].first, got));
    }
    return C;
  }
  int nextLeft(int cur, const vector<pair<int, int> > &A) {
    if (A.empty()) return cur;
    if (cur < A[0].first) return A[0].second;
    if (cur < A[1].first) return A[1].second;
    return Inf;
  }
  vector<pair<int, int> > joinRight(const vector<pair<int, int> > &A,
                                    const vector<pair<int, int> > &B) {
    vector<pair<int, int> > C;
    for (int i = 0; i < B.size(); i++) {
      int pnt = 0;
      while (pnt < A.size() && B[i].second < A[pnt].first) pnt++;
      int got = pnt < A.size() ? A[pnt].second : -Inf;
      C.push_back(pair<int, int>(B[i].first, got));
    }
    return C;
  }
  int nextRight(int cur, const vector<pair<int, int> > &A) {
    if (A.empty()) return cur;
    if (cur > A[0].first) return A[0].second;
    if (cur > A[1].first) return A[1].second;
    return -Inf;
  }
  void Left(int v) {
    mylef[v].clear();
    mylef[v].push_back(pair<int, int>(-p[v], -p[v]));
    mylef[v].push_back(pair<int, int>(p[v], p[v]));
    fromlef[v] = mylef[v];
    if (L[v]) {
      Left(L[v]);
      fromlef[v] = joinLeft(fromlef[L[v]], fromlef[v]);
    }
    if (R[v]) {
      Left(R[v]);
      fromlef[v] = joinLeft(fromlef[v], fromlef[R[v]]);
    }
  }
  void Right(int v) {
    myrig[v].clear();
    myrig[v].push_back(pair<int, int>(p[v], p[v]));
    myrig[v].push_back(pair<int, int>(-p[v], -p[v]));
    fromrig[v] = myrig[v];
    if (R[v]) {
      Right(R[v]);
      fromrig[v] = joinRight(fromrig[v], fromrig[R[v]]);
    }
    if (L[v]) {
      Right(L[v]);
      fromrig[v] = joinRight(fromrig[L[v]], fromrig[v]);
    }
  }
  void writeLeft(int v, int &cur) {
    if (v == 0) return;
    writeLeft(L[v], cur);
    res[v] = cur = nextLeft(cur, mylef[v]);
    writeLeft(R[v], cur);
  }
  void writeRight(int v, int &cur) {
    if (v == 0) return;
    writeRight(R[v], cur);
    res[v] = cur = nextRight(cur, myrig[v]);
    writeRight(L[v], cur);
  }
  bool Solve(int v, int mx, int mn) {
    if (mx >= Inf || mn <= -Inf) return false;
    if (v == 0) return true;
    if ((mx < p[v] || p[v] < nextRight(mn, fromrig[R[v]])) &&
        Solve(L[v], mx, min(p[v], nextRight(mn, fromrig[R[v]])))) {
      writeRight(R[v], mn);
      res[v] = p[v];
      return true;
    }
    if ((nextLeft(mx, fromlef[L[v]]) < -p[v] || -p[v] < mn) &&
        Solve(R[v], max(-p[v], nextLeft(mx, fromlef[L[v]])), mn)) {
      writeLeft(L[v], mx);
      res[v] = -p[v];
      return true;
    }
    return false;
  }
  int main() {
    scanf("%d", &T);
    while (T--) {
      scanf("%d", &n);
      for (int i = 1; i <= n; i++) scanf("%d", &p[i]);
      fill(L + 1, L + n + 1, 0);
      fill(R + 1, R + n + 1, 0);
      slen = 0;
      seq[slen++] = 1;
      for (int i = 2; i <= n; i++) {
        while (slen >= 2 && p[i] > p[seq[slen - 2]]) {
          R[seq[slen - 2]] = seq[slen - 1];
          slen--;
        }
        if (slen > 0 && p[i] > p[seq[slen - 1]]) {
          L[i] = seq[slen - 1];
          slen--;
        }
        seq[slen++] = i;
      }
      while (slen >= 2) {
        R[seq[slen - 2]] = seq[slen - 1];
        slen--;
      }
      root = seq[0];
      Left(root);
      Right(root);
      if (Solve(root, -Inf, Inf)) {
        printf("YES\n");
        for (int i = 1; i <= n; i++)
          printf("%d%c", res[i], i + 1 <= n ? ' ' : '\n');
      } else
        printf("NO\n");
    }
    return 0;
  }
  