Description: 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. Input Format: 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$$$. Output Format: 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. Note: None