#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;
}

### Prompt

Please create a solution in Cpp to the following problem:

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

### Response

```cpp
#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;
}

```