#include <iostream>
#include <assert.h>
using namespace std;
void printArray(int arr[], int n);
void rotate(int arr[],int start,int end)
{
  int temp = arr[end];
  while(start < end)
  {
    arr[end] = arr[end - 1];
    --end;
  }
  arr[start] = temp;
}

void rearrange(int arr[], int n)
{
    int i,j;
     // this for loop segregate the +ve and -ve Number
    for(i=0,j=0;j<n;++j)
    {
        if(arr[j] < 0)
        {
        rotate(arr,i,j);
        ++i;
        }
    }
    j = 0;
    
    // This while loop arranging +ve and -ve number 
    if(arr[j] < 0)
        ++j;
    while(i < n && j <= i)
    {
        rotate(arr,j,i);
        i = i + 1;
        j = j + 2;

    }
}

void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
      cout << arr[i] << " ";
    cout << endl;
}


int main()
{
   
    int arr[] = {-5, -2, 5, 2, 4, 7, 1, 8, 0, -8};
    int n = sizeof(arr)/sizeof(arr[0]);

    cout << "Given array is \n";
    printArray(arr, n);

    rearrange(arr, n);

    cout << "Rearranged array is \n";
    printArray(arr, n);

    return 0;
}