Segregate positive and negative elements in an array with O(1) complexity

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace OneCompiler
{
	public class Program
	{
		public static void Main(string[] args)
		{
			int n = int.Parse(Console.ReadLine());
			
			int[] arr = Array.ConvertAll(Console.ReadLine().Split(" "), new Converter<string,int>(StringToInteger));
			
			SegregateElements(arr);
			
			for (int i = 0; i < arr.Length; i++)
			{
			  Console.Write(arr[i] + " ");
			}
		}
		
		private static int StringToInteger(string s)
		{
		  return int.Parse(s);
		}
		
		private static int[] SegregateElements(int[] arr)
		{
		  int n = arr.Length;
		  
		  var outOfPlace = false;
		  var nextSign = string.Empty;
		  
		  for (int i = 0; i < n; i++)
		  {
		    if (i % 2 == 0)
		    {
		      outOfPlace = arr[i] >= 0 ? false : true;
		      nextSign = arr[i] >= 0 ? "negative" : "positive";
		    }
		    else
		    {
		      outOfPlace = arr[i] < 0 ? false : true;
		      nextSign = arr[i] < 0 ? "positive" : "negative";
		    }
		    
		    if (outOfPlace)
		    {
		      var currentSign = string.Empty;
		      
		      for (int j = i + 1; j < n; j++)
		      {
		        currentSign = arr[j] >= 0 ? "positive" : "negative";
		        
		        if (currentSign == nextSign)
		        {
		          Rotate(arr, i, j);
		          break;
		        }
		      }
		    }
		  }
		  
		  return arr;
		}
		
		public static void Rotate(int[] arr, int l, int r)
		{
		  var temp = arr[r];
		  
		  for (int i = r; i > l; i--)
		  {
		    arr[i] = arr[i - 1]; 
		  }
		  
		  arr[l] = temp;
		}
	}
}