#include <bits/stdc++.h>
using namespace std;
template <typename T>
using MinHeap = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using MaxHeap = priority_queue<T>;
const long double PI = 3.14159265358979323846;
const long double E = 2.718281828459;
const long double EPS = 1e-8;
long long pow2(long long n) { return 1ll << n; }
mt19937 rng(
    (unsigned int)chrono::steady_clock::now().time_since_epoch().count());
long long n;
long long idx(long long x, long long y) { return x * 2 * (n + 1) + y; }
pair<long long, long long> rev(long long idx) {
  long long x = idx / (2 * n + 2);
  long long y = idx % (2 * n + 2);
  return {x, y};
}
int main(int argn, char **argv) {
  ios::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);
  int T = 1;
  cin >> T;
  for (int(I) = (0); (I) <= ((T)-1); (I)++) {
    cin >> n;
    vector<long long> p(n);
    for (int(i) = (0); (i) <= ((n)-1); (i)++) cin >> p[i];
    stack<pair<long long, long long>> st;
    st.emplace(0, 0);
    map<long long, long long> last;
    bool found = true;
    for (int(i) = (0); (i) <= ((n)-1); (i)++) {
      vector<tuple<long long, long long, long long>> vec;
      while (!st.empty()) {
        auto [x, y] = st.top();
        st.pop();
        long long pre = idx(x, y);
        if (x < -p[i] + n + 1)
          vec.emplace_back(-p[i] + n + 1, y, pre);
        else if (x < p[i] + n + 1)
          vec.emplace_back(p[i] + n + 1, y, pre);
        if (y < -p[i] + n + 1)
          vec.emplace_back(x, -p[i] + n + 1, pre);
        else if (y < p[i] + n + 1)
          vec.emplace_back(x, p[i] + n + 1, pre);
      }
      sort((vec).begin(), (vec).end());
      for (auto [x, y, pre] : vec) {
        bool can = true;
        if (!st.empty()) {
          auto [x0, y0] = st.top();
          if (y >= y0) can = false;
        }
        if (can) st.emplace(x, y), last[idx(x, y)] = pre;
      }
      if (st.empty()) {
        found = false;
        break;
      };
    }
    if (found) {
      cout << "YES" << endl;
      vector<long long> sign(n, 1);
      auto [x, y] = st.top();
      long long a = x, b = y;
      long long crt = n - 1;
      while (1) {
        if (a == 0 && b == 0) break;
        ;
        if (a - (n + 1) + p[crt] == 0) sign[crt] = -1;
        if (b - (n + 1) + p[crt] == 0) sign[crt] = -1;
        long long pre = last[idx(a, b)];
        auto [x, y] = rev(pre);
        a = x, b = y, crt--;
      }
      for (int(i) = (0); (i) <= ((n)-1); (i)++) cout << p[i] * sign[i] << " ";
      cout << endl;
    } else
      cout << "NO" << endl;
  }
}

### 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>
using MinHeap = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using MaxHeap = priority_queue<T>;
const long double PI = 3.14159265358979323846;
const long double E = 2.718281828459;
const long double EPS = 1e-8;
long long pow2(long long n) { return 1ll << n; }
mt19937 rng(
    (unsigned int)chrono::steady_clock::now().time_since_epoch().count());
long long n;
long long idx(long long x, long long y) { return x * 2 * (n + 1) + y; }
pair<long long, long long> rev(long long idx) {
  long long x = idx / (2 * n + 2);
  long long y = idx % (2 * n + 2);
  return {x, y};
}
int main(int argn, char **argv) {
  ios::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);
  int T = 1;
  cin >> T;
  for (int(I) = (0); (I) <= ((T)-1); (I)++) {
    cin >> n;
    vector<long long> p(n);
    for (int(i) = (0); (i) <= ((n)-1); (i)++) cin >> p[i];
    stack<pair<long long, long long>> st;
    st.emplace(0, 0);
    map<long long, long long> last;
    bool found = true;
    for (int(i) = (0); (i) <= ((n)-1); (i)++) {
      vector<tuple<long long, long long, long long>> vec;
      while (!st.empty()) {
        auto [x, y] = st.top();
        st.pop();
        long long pre = idx(x, y);
        if (x < -p[i] + n + 1)
          vec.emplace_back(-p[i] + n + 1, y, pre);
        else if (x < p[i] + n + 1)
          vec.emplace_back(p[i] + n + 1, y, pre);
        if (y < -p[i] + n + 1)
          vec.emplace_back(x, -p[i] + n + 1, pre);
        else if (y < p[i] + n + 1)
          vec.emplace_back(x, p[i] + n + 1, pre);
      }
      sort((vec).begin(), (vec).end());
      for (auto [x, y, pre] : vec) {
        bool can = true;
        if (!st.empty()) {
          auto [x0, y0] = st.top();
          if (y >= y0) can = false;
        }
        if (can) st.emplace(x, y), last[idx(x, y)] = pre;
      }
      if (st.empty()) {
        found = false;
        break;
      };
    }
    if (found) {
      cout << "YES" << endl;
      vector<long long> sign(n, 1);
      auto [x, y] = st.top();
      long long a = x, b = y;
      long long crt = n - 1;
      while (1) {
        if (a == 0 && b == 0) break;
        ;
        if (a - (n + 1) + p[crt] == 0) sign[crt] = -1;
        if (b - (n + 1) + p[crt] == 0) sign[crt] = -1;
        long long pre = last[idx(a, b)];
        auto [x, y] = rev(pre);
        a = x, b = y, crt--;
      }
      for (int(i) = (0); (i) <= ((n)-1); (i)++) cout << p[i] * sign[i] << " ";
      cout << endl;
    } else
      cout << "NO" << endl;
  }
}

```