Bipartite Array
Contest: Educational Codeforces Round 119 (Rated for Div. 2)
Difficulty rating: 2800
Tags: dp, greedy

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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example output:
YES
1 2 3
NO
YES
-4 -1 -3 -2
YES
-3 -2 1 6 7 -8 -5 -4

Editorial:
To begin with, let's understand that an array is bipartite if and only if there is no decreasing subsequence of length $$$3$$$ in the array.
Now we can write dynamic programming $$$dp_{i, x, y}$$$: is there an array $$$a$$$ of length $$$i$$$ such that $$$x$$$ is the maximum last element of a decreasing subsequence of length $$$1$$$, and $$$y$$$ is the maximum last element of a subsequence of length $$$2$$$. Note that $$$x > y$$$.
Let's consider all possible transitions from the state $$$(i, x, y)$$$ if we are trying to put the number $$$z$$$ on the $$$i$$$-th position, where $$$z = \pm p_i$$$:
• if $$$z > x$$$, then the new state will be $$$(i +1, z,y)$$$;
• if $$$z > y$$$, then the new state will be $$$(i + 1, x, z)$$$;
• if $$$z < y$$$, then such a transition is not valid, because a decreasing subsequence of length $$$3$$$ is formed in the array.
With a naive implementation, such dynamic programming works in $$$O(n^3)$$$.
We can note that for fixed values of $$$i$$$ and $$$x$$$ ($$$i$$$ and $$$y$$$) it is enough for us to store only the minimum available value of $$$y$$$ ($$$x$$$). So, we can write dynamic programming $$$dp_{i, x}$$$, which is defined similarly to the above, but now instead of being Boolean, stores the minimum value of $$$y$$$ (or infinity if the state is not valid).
We have speeded up our solution to $$$O(n^2)$$$, but it is still too slow.
To speed up the solution even more, we have to look at the transitions in dynamics and notice that for a fixed $$$i$$$, either $$$x$$$ or $$$y$$$ is always equal to $$$\pm p_{i - 1}$$$. So we can rewrite our dynamic programming in the following form — $$$dp_{i, pos, sign}$$$. Here, the $$$pos$$$ flag says which of the numbers $$$x$$$ and $$$y$$$ is equal to $$$\pm p_{i - 1}$$$, and the $$$sign$$$ flag is responsible for the sign of $$$p_{i - 1}$$$, and the minimum value of $$$y$$$ or $$$x$$$ is stored in the value itself (depending on $$$pos$$$).
Thus, we got a solution with a linear running time.
In fact, this solution can be simplified if we see the following relation: the number we use on position $$$i$$$ is not less than $$$dp_{i, 0, sign}$$$ and not greater than $$$dp_{i, 1, sign}$$$. This allows us to get rid of one of the states in our dynamic programming altogether, so we get an easier solution. This optimization wasn't required to get AC, but the code becomes shorter.