description: 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
solution: /*
  Hello Its Gokulraja
   */
  import static java.lang.Math.*;
  import java.util.*;
  import java.io.*;
  import java.math.*;
  
  public class x1620F
  {
      static final int INF = Integer.MAX_VALUE/2;
      public static void main(String hi[]) throws Exception
      {
          BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer st = new StringTokenizer(infile.readLine());
          int T = Integer.parseInt(st.nextToken());
          StringBuilder sb = new StringBuilder();
          while(T-->0)
          {
              st = new StringTokenizer(infile.readLine());
              int N = Integer.parseInt(st.nextToken());
              int[] arr = readArr(N, infile, st);
              if(N <= 2)
              {
                  sb.append("YES\n");
                  for(int x: arr)
                      sb.append(x+" ");
                  sb.append("\n");
                  continue;
              }
              ArrayList<State> curr = new ArrayList<State>();
              curr.add(new State(arr[0], -INF, arr[0], null));
              curr.add(new State(-arr[0], -INF, -arr[0], null));
              for(int i=1; i < N; i++)
              {
                  ArrayList<State> next = new ArrayList<State>();
                  for(int m=-1; m <= 1; m+=2)
                  {
                      int val = arr[i]*m;
                      for(State prev: curr)
                      {
                          if(val > prev.x)
                              next.add(new State(val, prev.y, val, prev));
                          else if(val > prev.y)
                              next.add(new State(prev.x, val, val, prev));
                      }
                  }
                  boolean[] useful = new boolean[next.size()];
                  Arrays.fill(useful, true);
                  Collections.sort(next, (x,y) -> {
                      if(x.x != y.x)
                          return Integer.compare(x.x, y.x);
                      return Integer.compare(x.y, y.y);
                  });
                  for(int aa=0; aa < next.size(); aa++)
                      for(int bb=aa+1; bb < next.size(); bb++)
                      {
                          State b = next.get(aa);
                          State a = next.get(bb);
                          if(a.x >= b.x && a.y >= b.y)
                          {
                              useful[bb] = false;
                              break;
                          }
                      }
                  curr.clear();
                  for(int a=0; a < next.size(); a++)
                      if(useful[a])
                          curr.add(next.get(a));
              }
              if(curr.size() == 0)
                  sb.append("NO\n");
              else
              {
                  sb.append("YES\n");
                  ArrayList<Integer> res = new ArrayList<Integer>();
                  State node = curr.get(0);
                  while(node != null)
                  {
                      res.add(node.val);
                      node = node.parent;
                  }
                  Collections.reverse(res);
                  for(int x: res)
                      sb.append(x+" ");
                  sb.append("\n");
              }
          }
          System.out.print(sb);
      }
      public static int[] readArr(int N, BufferedReader infile, StringTokenizer st) throws Exception
      {
          int[] arr = new int[N];
          st = new StringTokenizer(infile.readLine());
          for(int i=0; i < N; i++)
              arr[i] = Integer.parseInt(st.nextToken());
          return arr;
      }
  }
  class State
  {
      public int x;
      public int y;
      public int val;
      public State parent;
  
      public State(int a, int b, int t, State par)
      {
          x = a;
          y = b;
          val = t;
          parent = par;
      }
      public String toString()
      {
          return "info: "+x+" "+y+" "+val;
      }
  }