CF1620F Bipartite Array

You are given a permutation $ p $ consisting of $ n $ integers $ 1, 2, \dots, 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.

The first line contains a single integer $ t $ ( $ 1 \le t \le 2 \cdot 10^5 $ ) — the number of test cases. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 10^6 $ ) — the size of the permutation. The second line contains $ n $ integers $ p_1, p_2, \dots, p_n $ . The sum of $ n $ over all test cases doesn't exceed $ 10^6 $ .

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.