Rearrange Array: Move Negative Numbers to the Beginning

Given an array ARR consisting of N integers, rearrange the elements such that all negative numbers are located before all positive numbers. The order of elements in each category (negative or positive) does not matter.

Can you achieve this with O(1) auxiliary space?

Input:

The very first line of input contains an integer ‘T’ denoting the number of test cases.
The first line of every test case contains an integer ‘N’, the number of elements in the array.
The second line of every test case contains ‘N’ space-separated integers which are the elements of the array.

Output:

For each test case, output “Yes” if the rearranged array is correct as per the problem statement, otherwise print “No”. Each test case result is printed on a new line.

Example:

Input:
array = [1, 2, -3, 4, -4, -5]
Output:
[-3, -5, -4, 2, 4, 1]
- or any other arrangement where all negative numbers come before positives.

Constraints:

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 5 * 104
• -105 ≤ ARR[i] ≤ 105
• Time Limit: 1 sec

Note:

No need to print the results yourself, just return the resulting array as per the problem's requirements.