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

### Prompt

Your task is to create a cpp solution 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;
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;
}

```