#include <bits/stdc++.h>
using namespace std;
template <typename T>
class vec : public vector<T> {
 public:
  int delta;
  vec(int n) : vector<T>(2 * n + 1), delta(n) {}
  vec(int n, T x) : vector<T>(2 * n + 1, x), delta(n) {}
  T &operator[](int i) { return vector<T>::operator[](i + delta); }
};
void solve(int test_ind) {
  int n;
  scanf("%d", &n);
  vector<int> a(n), p(n);
  for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
  if (n == 1) {
    printf("YES\n%d\n", a[0]);
    return;
  }
  const int MAX = 1000000000;
  const int MIN = -MAX;
  vector<vector<int> > dp(n, vector<int>(4, MAX));
  vector<vector<int> > prev(n, vector<int>(4, -1));
  dp[0][0] = MIN;
  dp[0][2] = MIN;
  for (int i = 1; i < n; ++i) {
    for (int ind2 = 0; ind2 < 4; ++ind2) {
      int cur = a[i];
      bool first = true;
      if (ind2 < 2) cur = -a[i];
      if (ind2 & 1) first = false;
      int ind = -1;
      for (int ind1 = 0; ind1 < 4; ++ind1) {
        int prvmx, prvsec;
        if (ind1 == 0) {
          prvmx = -a[i - 1];
          prvsec = dp[i - 1][0];
        } else if (ind1 == 1) {
          prvmx = dp[i - 1][1];
          prvsec = -a[i - 1];
        } else if (ind1 == 2) {
          prvmx = a[i - 1];
          prvsec = dp[i - 1][2];
        } else {
          prvmx = dp[i - 1][3];
          prvsec = a[i - 1];
        }
        if (first) {
          if (prvmx < cur) {
            if (prvsec < dp[i][ind2]) {
              dp[i][ind2] = prvsec;
              ind = ind1;
            }
          }
        } else {
          if (prvmx > cur && prvsec < cur) {
            if (dp[i][ind2] > prvmx) {
              dp[i][ind2] = prvmx;
              ind = ind1;
            }
          }
        }
      }
      if (ind != -1) prev[i][ind2] = ind;
    }
  }
  int ind1 = -1;
  for (int ind = 0; ind < 4; ++ind) {
    if (prev[n - 1][ind] != -1) {
      ind1 = ind;
      break;
    }
  }
  if (ind1 == -1) {
    printf("NO\n");
    return;
  }
  for (int i = n - 1; i >= 0; --i) {
    p[i] = ind1 < 2 ? -a[i] : a[i];
    ind1 = prev[i][ind1];
  }
  printf("YES\n");
  for (int i = 0; i < n; ++i) {
    printf("%d ", p[i]);
  }
  printf("\n");
}
int main() {
  int t = 1;
  cin >> t;
  for (int i = 0; i < t; i++) {
    solve(i);
  }
  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;
template <typename T>
class vec : public vector<T> {
 public:
  int delta;
  vec(int n) : vector<T>(2 * n + 1), delta(n) {}
  vec(int n, T x) : vector<T>(2 * n + 1, x), delta(n) {}
  T &operator[](int i) { return vector<T>::operator[](i + delta); }
};
void solve(int test_ind) {
  int n;
  scanf("%d", &n);
  vector<int> a(n), p(n);
  for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
  if (n == 1) {
    printf("YES\n%d\n", a[0]);
    return;
  }
  const int MAX = 1000000000;
  const int MIN = -MAX;
  vector<vector<int> > dp(n, vector<int>(4, MAX));
  vector<vector<int> > prev(n, vector<int>(4, -1));
  dp[0][0] = MIN;
  dp[0][2] = MIN;
  for (int i = 1; i < n; ++i) {
    for (int ind2 = 0; ind2 < 4; ++ind2) {
      int cur = a[i];
      bool first = true;
      if (ind2 < 2) cur = -a[i];
      if (ind2 & 1) first = false;
      int ind = -1;
      for (int ind1 = 0; ind1 < 4; ++ind1) {
        int prvmx, prvsec;
        if (ind1 == 0) {
          prvmx = -a[i - 1];
          prvsec = dp[i - 1][0];
        } else if (ind1 == 1) {
          prvmx = dp[i - 1][1];
          prvsec = -a[i - 1];
        } else if (ind1 == 2) {
          prvmx = a[i - 1];
          prvsec = dp[i - 1][2];
        } else {
          prvmx = dp[i - 1][3];
          prvsec = a[i - 1];
        }
        if (first) {
          if (prvmx < cur) {
            if (prvsec < dp[i][ind2]) {
              dp[i][ind2] = prvsec;
              ind = ind1;
            }
          }
        } else {
          if (prvmx > cur && prvsec < cur) {
            if (dp[i][ind2] > prvmx) {
              dp[i][ind2] = prvmx;
              ind = ind1;
            }
          }
        }
      }
      if (ind != -1) prev[i][ind2] = ind;
    }
  }
  int ind1 = -1;
  for (int ind = 0; ind < 4; ++ind) {
    if (prev[n - 1][ind] != -1) {
      ind1 = ind;
      break;
    }
  }
  if (ind1 == -1) {
    printf("NO\n");
    return;
  }
  for (int i = n - 1; i >= 0; --i) {
    p[i] = ind1 < 2 ? -a[i] : a[i];
    ind1 = prev[i][ind1];
  }
  printf("YES\n");
  for (int i = 0; i < n; ++i) {
    printf("%d ", p[i]);
  }
  printf("\n");
}
int main() {
  int t = 1;
  cin >> t;
  for (int i = 0; i < t; i++) {
    solve(i);
  }
  return 0;
}

```