#include <bits/stdc++.h>
using std::make_pair;
using std::pair;
using std::reverse;
using std::set;
using std::sort;
using std::swap;
using std::vector;
const int32_t oo = 1e9;
template <typename T>
T min(std::initializer_list<T> l) {
  const T* it = l.begin();
  const T* end = l.end();
  T answer = *it;
  it++;
  while (it != end) {
    if (*it < answer) answer = *it;
    it++;
  }
  return answer;
}
template <typename T>
T max(std::initializer_list<T> l) {
  const T* it = l.begin();
  const T* end = l.end();
  T answer = *it;
  it++;
  while (it != end) {
    if (*it > answer) answer = *it;
    it++;
  }
  return answer;
}
class all_binaries_iterator {
 private:
  bool end;
  vector<int> v;

 public:
  all_binaries_iterator(int n) {
    end = false;
    v.resize(n, 0);
  }
  bool operator!=(const all_binaries_iterator r) const { return !end; }
  const vector<int>& operator*() const { return v; }
  const all_binaries_iterator& operator++() {
    unsigned int ind = 0;
    while (ind < v.size() && v[ind] == 1) v[ind++] = 0;
    if (ind == v.size())
      end = true;
    else
      v[ind] = 1;
    return *this;
  }
};
class all_binaries {
 private:
  int n;

 public:
  all_binaries(int n) : n(n) {}
  all_binaries_iterator begin() const { return all_binaries_iterator(n); }
  all_binaries_iterator end() const { return all_binaries_iterator(0); }
};
class all_permutations_iterator {
 private:
  vector<int> v;

 public:
  all_permutations_iterator(int n) {
    v.resize(n);
    for (int i = 1; i <= n; i++) v[i - 1] = i;
  }
  bool operator!=(const all_permutations_iterator r) const {
    for (unsigned int i = 0; i < v.size() - 1; i++)
      if (v[i] < v[i + 1]) return true;
    return false;
  }
  const vector<int>& operator*() const { return v; }
  const all_permutations_iterator& operator++() {
    unsigned int indx = v.size() - 2;
    while (v[indx] > v[indx + 1]) indx--;
    unsigned int smallest_larger = indx + 1;
    while (smallest_larger + 1 < v.size() && v[smallest_larger + 1] > v[indx])
      smallest_larger++;
    swap(v[indx], v[smallest_larger]);
    reverse(v.begin() + indx + 1, v.end());
    return *this;
  }
};
class all_permutations {
 private:
  int n;

 public:
  all_permutations(int n) : n(n) {}
  all_permutations_iterator begin() const {
    return all_permutations_iterator(n);
  }
  all_permutations_iterator end() const { return all_permutations_iterator(0); }
};
const int max_size = 1e6;
bool brute_force(int* a, int n) {
  for (auto bin : all_binaries(n)) {
    for (int i = 0; i < n; i++) {
      if ((a[i] < 0 && bin[i] == 0) || (a[i] > 0 && bin[i] == 1)) a[i] = -a[i];
    }
    bool good_solution = true;
    for (int i = 0; i < n; i++)
      for (int j = i + 1; j < n; j++)
        if (a[i] > a[j])
          for (int k = j + 1; k < n; k++)
            if (a[j] > a[k]) good_solution = false;
    if (good_solution) return true;
  }
  return false;
}
int gi(int ind, int n) { return ind + n + 1; }
bool dp_n3(int* a, int n) {
  bool DP[n][2 * n + 2][2 * n + 2];
  for (int i = 0; i < n; i++)
    for (int j = 0; j < 2 * n + 2; j++)
      for (int k = 0; k < 2 * n + 2; k++) DP[i][j][k] = false;
  DP[0][gi(a[0], n)][0] = true;
  DP[0][gi(-a[0], n)][0] = true;
  for (int i = 0; i < n - 1; i++)
    for (int j = -n - 1; j <= n; j++)
      for (int k = -n - 1; k <= n; k++)
        if (DP[i][gi(j, n)][gi(k, n)]) {
          if (a[i + 1] > j) DP[i + 1][gi(a[i + 1], n)][gi(k, n)] = true;
          if (a[i + 1] > k) DP[i + 1][gi(j, n)][gi(a[i + 1], n)] = true;
          if (-a[i + 1] > j) DP[i + 1][gi(-a[i + 1], n)][gi(k, n)] = true;
          if (-a[i + 1] > k) DP[i + 1][gi(j, n)][gi(-a[i + 1], n)] = true;
        }
  for (int j = -n - 1; j <= n; j++)
    for (int k = -n - 1; k <= n; k++)
      if (DP[n - 1][gi(j, n)][gi(k, n)]) return true;
  return false;
}
bool dp_n2(int* a, int n) {
  int DP[n][2 * n + 2];
  for (int i = 0; i < n; i++)
    for (int j = 0; j < 2 * n + 2; j++) DP[i][j] = oo;
  DP[0][gi(a[0], n)] = -oo;
  DP[0][gi(-a[0], n)] = -oo;
  for (int i = 0; i < n - 1; i++)
    for (int j = -n - 1; j <= n; j++)
      if (DP[i][gi(j, n)] != oo) {
        if (a[i + 1] > j)
          DP[i + 1][gi(a[i + 1], n)] =
              min({DP[i + 1][gi(a[i + 1], n)], DP[i][gi(j, n)]});
        else if (a[i + 1] > DP[i][gi(j, n)])
          DP[i + 1][gi(j, n)] = min({DP[i + 1][gi(j, n)], a[i + 1]});
        if (-a[i + 1] > j)
          DP[i + 1][gi(-a[i + 1], n)] =
              min({DP[i + 1][gi(-a[i + 1], n)], DP[i][gi(j, n)]});
        else if (-a[i + 1] > DP[i][gi(j, n)])
          DP[i + 1][gi(j, n)] = min({DP[i + 1][gi(j, n)], -a[i + 1]});
      }
  for (int j = 0; j < 2 * n + 2; j++)
    if (DP[n - 1][j] != oo) return true;
  return false;
}
bool dp_n(int* a, int n) {
  int DP[n][2];
  int prev[n][2];
  DP[0][0] = -oo;
  DP[0][1] = -oo;
  for (int i = 1; i < n; i++) {
    DP[i][0] = DP[i][1] = oo;
    if (-a[i] > DP[i - 1][0])
      if (DP[i][0] > -a[i - 1]) {
        DP[i][0] = -a[i - 1];
        prev[i][0] = 0;
      }
    if (-a[i] > DP[i - 1][1])
      if (DP[i][0] > a[i - 1]) {
        DP[i][0] = a[i - 1];
        prev[i][0] = 1;
      }
    if (-a[i] > -a[i - 1])
      if (DP[i][0] > DP[i - 1][0]) {
        DP[i][0] = DP[i - 1][0];
        prev[i][0] = 0;
      }
    if (-a[i] > a[i - 1])
      if (DP[i][0] > DP[i - 1][1]) {
        DP[i][0] = DP[i - 1][1];
        prev[i][0] = 1;
      }
    if (a[i] > DP[i - 1][0])
      if (DP[i][1] > -a[i - 1]) {
        DP[i][1] = -a[i - 1];
        prev[i][1] = 0;
      }
    if (a[i] > DP[i - 1][1])
      if (DP[i][1] > a[i - 1]) {
        DP[i][1] = a[i - 1];
        prev[i][1] = 1;
      }
    if (a[i] > -a[i - 1])
      if (DP[i][1] > DP[i - 1][0]) {
        DP[i][1] = DP[i - 1][0];
        prev[i][1] = 0;
      }
    if (a[i] > a[i - 1])
      if (DP[i][1] > DP[i - 1][1]) {
        DP[i][1] = DP[i - 1][1];
        prev[i][1] = 1;
      }
  }
  if (DP[n - 1][0] == oo && DP[n - 1][1] == oo) return false;
  int next = prev[n - 1][1];
  if (DP[n - 1][0] != oo) {
    next = prev[n - 1][0];
    a[n - 1] = -a[n - 1];
  }
  for (int i = n - 2; i >= 0; i--) {
    if (next == 0) a[i] = -a[i];
    next = prev[i][next];
  }
  return true;
}
int main() {
  int q, n;
  int a[max_size];
  [&] { return scanf("%d", &q); }();
  ;
  while (q--) {
    [&] { return scanf("%d", &n); }();
    ;
    for (int i = 0; i < n; i++) [&] { return scanf("%d", &a[i]); }();
    ;
    bool result = dp_n(a, n);
    if (result) {
      printf("YES\n");
      for (int i = 0; i < n; i++) printf("%d ", a[i]);
      printf("\n");
    } else
      printf("NO\n");
  }
  return 0;
}

### Prompt

Create a solution in CPP for 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 std::make_pair;
using std::pair;
using std::reverse;
using std::set;
using std::sort;
using std::swap;
using std::vector;
const int32_t oo = 1e9;
template <typename T>
T min(std::initializer_list<T> l) {
  const T* it = l.begin();
  const T* end = l.end();
  T answer = *it;
  it++;
  while (it != end) {
    if (*it < answer) answer = *it;
    it++;
  }
  return answer;
}
template <typename T>
T max(std::initializer_list<T> l) {
  const T* it = l.begin();
  const T* end = l.end();
  T answer = *it;
  it++;
  while (it != end) {
    if (*it > answer) answer = *it;
    it++;
  }
  return answer;
}
class all_binaries_iterator {
 private:
  bool end;
  vector<int> v;

 public:
  all_binaries_iterator(int n) {
    end = false;
    v.resize(n, 0);
  }
  bool operator!=(const all_binaries_iterator r) const { return !end; }
  const vector<int>& operator*() const { return v; }
  const all_binaries_iterator& operator++() {
    unsigned int ind = 0;
    while (ind < v.size() && v[ind] == 1) v[ind++] = 0;
    if (ind == v.size())
      end = true;
    else
      v[ind] = 1;
    return *this;
  }
};
class all_binaries {
 private:
  int n;

 public:
  all_binaries(int n) : n(n) {}
  all_binaries_iterator begin() const { return all_binaries_iterator(n); }
  all_binaries_iterator end() const { return all_binaries_iterator(0); }
};
class all_permutations_iterator {
 private:
  vector<int> v;

 public:
  all_permutations_iterator(int n) {
    v.resize(n);
    for (int i = 1; i <= n; i++) v[i - 1] = i;
  }
  bool operator!=(const all_permutations_iterator r) const {
    for (unsigned int i = 0; i < v.size() - 1; i++)
      if (v[i] < v[i + 1]) return true;
    return false;
  }
  const vector<int>& operator*() const { return v; }
  const all_permutations_iterator& operator++() {
    unsigned int indx = v.size() - 2;
    while (v[indx] > v[indx + 1]) indx--;
    unsigned int smallest_larger = indx + 1;
    while (smallest_larger + 1 < v.size() && v[smallest_larger + 1] > v[indx])
      smallest_larger++;
    swap(v[indx], v[smallest_larger]);
    reverse(v.begin() + indx + 1, v.end());
    return *this;
  }
};
class all_permutations {
 private:
  int n;

 public:
  all_permutations(int n) : n(n) {}
  all_permutations_iterator begin() const {
    return all_permutations_iterator(n);
  }
  all_permutations_iterator end() const { return all_permutations_iterator(0); }
};
const int max_size = 1e6;
bool brute_force(int* a, int n) {
  for (auto bin : all_binaries(n)) {
    for (int i = 0; i < n; i++) {
      if ((a[i] < 0 && bin[i] == 0) || (a[i] > 0 && bin[i] == 1)) a[i] = -a[i];
    }
    bool good_solution = true;
    for (int i = 0; i < n; i++)
      for (int j = i + 1; j < n; j++)
        if (a[i] > a[j])
          for (int k = j + 1; k < n; k++)
            if (a[j] > a[k]) good_solution = false;
    if (good_solution) return true;
  }
  return false;
}
int gi(int ind, int n) { return ind + n + 1; }
bool dp_n3(int* a, int n) {
  bool DP[n][2 * n + 2][2 * n + 2];
  for (int i = 0; i < n; i++)
    for (int j = 0; j < 2 * n + 2; j++)
      for (int k = 0; k < 2 * n + 2; k++) DP[i][j][k] = false;
  DP[0][gi(a[0], n)][0] = true;
  DP[0][gi(-a[0], n)][0] = true;
  for (int i = 0; i < n - 1; i++)
    for (int j = -n - 1; j <= n; j++)
      for (int k = -n - 1; k <= n; k++)
        if (DP[i][gi(j, n)][gi(k, n)]) {
          if (a[i + 1] > j) DP[i + 1][gi(a[i + 1], n)][gi(k, n)] = true;
          if (a[i + 1] > k) DP[i + 1][gi(j, n)][gi(a[i + 1], n)] = true;
          if (-a[i + 1] > j) DP[i + 1][gi(-a[i + 1], n)][gi(k, n)] = true;
          if (-a[i + 1] > k) DP[i + 1][gi(j, n)][gi(-a[i + 1], n)] = true;
        }
  for (int j = -n - 1; j <= n; j++)
    for (int k = -n - 1; k <= n; k++)
      if (DP[n - 1][gi(j, n)][gi(k, n)]) return true;
  return false;
}
bool dp_n2(int* a, int n) {
  int DP[n][2 * n + 2];
  for (int i = 0; i < n; i++)
    for (int j = 0; j < 2 * n + 2; j++) DP[i][j] = oo;
  DP[0][gi(a[0], n)] = -oo;
  DP[0][gi(-a[0], n)] = -oo;
  for (int i = 0; i < n - 1; i++)
    for (int j = -n - 1; j <= n; j++)
      if (DP[i][gi(j, n)] != oo) {
        if (a[i + 1] > j)
          DP[i + 1][gi(a[i + 1], n)] =
              min({DP[i + 1][gi(a[i + 1], n)], DP[i][gi(j, n)]});
        else if (a[i + 1] > DP[i][gi(j, n)])
          DP[i + 1][gi(j, n)] = min({DP[i + 1][gi(j, n)], a[i + 1]});
        if (-a[i + 1] > j)
          DP[i + 1][gi(-a[i + 1], n)] =
              min({DP[i + 1][gi(-a[i + 1], n)], DP[i][gi(j, n)]});
        else if (-a[i + 1] > DP[i][gi(j, n)])
          DP[i + 1][gi(j, n)] = min({DP[i + 1][gi(j, n)], -a[i + 1]});
      }
  for (int j = 0; j < 2 * n + 2; j++)
    if (DP[n - 1][j] != oo) return true;
  return false;
}
bool dp_n(int* a, int n) {
  int DP[n][2];
  int prev[n][2];
  DP[0][0] = -oo;
  DP[0][1] = -oo;
  for (int i = 1; i < n; i++) {
    DP[i][0] = DP[i][1] = oo;
    if (-a[i] > DP[i - 1][0])
      if (DP[i][0] > -a[i - 1]) {
        DP[i][0] = -a[i - 1];
        prev[i][0] = 0;
      }
    if (-a[i] > DP[i - 1][1])
      if (DP[i][0] > a[i - 1]) {
        DP[i][0] = a[i - 1];
        prev[i][0] = 1;
      }
    if (-a[i] > -a[i - 1])
      if (DP[i][0] > DP[i - 1][0]) {
        DP[i][0] = DP[i - 1][0];
        prev[i][0] = 0;
      }
    if (-a[i] > a[i - 1])
      if (DP[i][0] > DP[i - 1][1]) {
        DP[i][0] = DP[i - 1][1];
        prev[i][0] = 1;
      }
    if (a[i] > DP[i - 1][0])
      if (DP[i][1] > -a[i - 1]) {
        DP[i][1] = -a[i - 1];
        prev[i][1] = 0;
      }
    if (a[i] > DP[i - 1][1])
      if (DP[i][1] > a[i - 1]) {
        DP[i][1] = a[i - 1];
        prev[i][1] = 1;
      }
    if (a[i] > -a[i - 1])
      if (DP[i][1] > DP[i - 1][0]) {
        DP[i][1] = DP[i - 1][0];
        prev[i][1] = 0;
      }
    if (a[i] > a[i - 1])
      if (DP[i][1] > DP[i - 1][1]) {
        DP[i][1] = DP[i - 1][1];
        prev[i][1] = 1;
      }
  }
  if (DP[n - 1][0] == oo && DP[n - 1][1] == oo) return false;
  int next = prev[n - 1][1];
  if (DP[n - 1][0] != oo) {
    next = prev[n - 1][0];
    a[n - 1] = -a[n - 1];
  }
  for (int i = n - 2; i >= 0; i--) {
    if (next == 0) a[i] = -a[i];
    next = prev[i][next];
  }
  return true;
}
int main() {
  int q, n;
  int a[max_size];
  [&] { return scanf("%d", &q); }();
  ;
  while (q--) {
    [&] { return scanf("%d", &n); }();
    ;
    for (int i = 0; i < n; i++) [&] { return scanf("%d", &a[i]); }();
    ;
    bool result = dp_n(a, n);
    if (result) {
      printf("YES\n");
      for (int i = 0; i < n; i++) printf("%d ", a[i]);
      printf("\n");
    } else
      printf("NO\n");
  }
  return 0;
}

```