AlgoUniversity
  • Go Back
Discussion
Alternating Numbers :

Author

admin

Difficulty Level : Easy

Submissions : 624

Asked In : Amazon

Marks :10

: 6 | : 0

You are given a zero indexed array of $$$n$$$ integers. You need to rearrange the elements of the array in such a way that positive and negative numbers are placed alternatively at the begining of the array and the length of the prefix $$$k$$$ where $$$a_i*a_{i-1}<0$$$ for each $$$i(1 \leq i \leq k)$$$ is maximum. If there are more positive of negative numbers they are placed at the end of the array. If there are multiple solutions, output any.

Input

The first line contains a single integer $$$n(1 \leq n \leq 10^5)$$$.

The next line contains $$$n$$$ space separated integers $$$a_1,a_2,...,a_n(-10^9 \leq a_i \leq 10^9)$$$ and $$$a_i!=0$$$.

Output

Output $$$n$$$ integers - the resultant array.

Example

Input
5
1 2 3 -4 5
Output
1 -4 2 3 5 

You need to login to view your submissions.

You need to login to view all submissions.

Loading...

Result : Executed

Loading...

Feel something is wrong with the test cases?

Result : Accepted

Test Cases :

You need to Log In
We're glad that you want to attempt this problem!

But to Run or Submit the Problem, you need to Log In.

Continue to Log In
Challenge Submitted!

Your challenge has been submitted successfully.

You will get a response soon via WhatsApp or Email.

Challenge
Facing issue while trying to solve the problem! Don't worry, we got you covered!

Do let us know your issue.

Looks good!
Please enter your issue / feedback.

How do we get in touch with you?
Looks good!
Please enter your phone no.
Looks good!
Please enter your email address.