2026. Me first
Sardor and Timur have two tables, each one has N cards on them. Cards of both tables have no difference.
Each card is written some number on both sides of it. If the number on the visible side of it is x, the number on the back side of it is −1−x.
They really wanted to play a game so they come up with rules of the game:
- When we maximize the product of numbers on the visible side of all cards, what will be the difference from initial pruduct?
In order to achieve this, you can make only one type of operation: turn the card over!
Sardor started playing the game by calculating in brain, but, fortunately Timur has his computer in his bag.
He tried to write a program but his algorithm is so slow that, if he waits for the program to work, Sardor will be able to win before. So he is asking for your help!?
Input
First line contains one integer, the number of cards on one table, N : (1≤N≤2∗105)(1≤N≤2∗105)
Second line contains NN numbers, which are the numbers on the cards on Timur's table: (−5∗105≤xi≤5∗105)(−5∗105≤xi≤5∗105)
Output
You are asked to find the numbers on the visible side of cards in order, when you achieve the maximum product. If there are multiple answers, print any of them.
Sample input 1
3 -9 -8 -7
Sample output 1
8 -8 -7
Sample input 2
5 -10 -10 -10 -10 -2
Sample output 2
-10 -10 -10 9 -2
Login to be able to submit.