median problem

The median of M numbers is defined as the middle number after sorting them in order if M is odd or the average number of the middle 2 numbers (again after sorting) if M is even. You have an empty number list at first. Then you can add or remove some number from the list. For each add or remove operation, output the median of numbers in the list.
Example : For a set of m = 5 numbers, { 9, 2, 8, 4, 1 } the median is the third number in sorted set { 1, 2, 4, 8, 9 } which is 4. Similarly for set of m = 4, { 5, 2, 10, 4 }, the median is the average of second and the third element in the sorted set { 2, 4, 5, 10 } which is (4+5)/2 = 4.5
Input:
The first line is an integer n indicates the number of operations. Each of the next n lines is either “a x” or “r x” which indicates the operation is add or remove.
Output:
For each operation: If the operation is add output the median after adding x in a single line. If the operation is remove and the number x is not in the list, output “Wrong!” in a single line. If the operation is remove and the number x is in the list, output the median after deleting x in a single line. (if the result is an integer DO NOT output decimal point. And if the result is a double number , DO NOT output trailing 0s.)
Constraints:
0 < n <= 100,000
for each “a x” or “r x”, x will always be an integer which will fit in 32 bits (unsigned)
Sample Input:
7
r 1
a 1
a 2
a 1
r 1
r 2
r 1
Sample Output:
Wrong!
1
1.5
1
1.5
1
Wrong!
Note: As evident from the last line of the input, if after remove operation the list becomes empty you have to print “Wrong!” ( quotes are for clarity ).



using System;
using System.Collections.Generic;
using System.IO;
using System.Text;
class Solution
{
    private static List list = new List();
    private static int count = 0;
    private static long min = long.MaxValue;
    private static long max = long.MinValue;
    private static long sum = 0;
    private static int mid = 0;
    private static int MedianIndex = 0;
    private static double MedianValue = 0;
    static void Main(String[] args)
    {
        int N = Convert.ToInt32(Console.ReadLine());
        int[] x = new int[N];
        string[] s = new string[N];
        string[] split = new string[2];
        for (int i = 0; i < N; i++)
        {
            split = Console.ReadLine().Split(new Char[] { ' ', '\t', '\n' });
            s[i] = split[0].Trim();
            x[i] = Convert.ToInt32(split[1].Trim());
        }
        for (int i = 0; i < N; i++)
        {
            if (s[i] == "a")
            {
                if (x[i] <= min)
                {
                    min = x[i];
                    list.Insert(0, x[i]);
                }
                else if (x[i] >= max)
                {
                    max = x[i];
                    list.Add(x[i]);
                }
                else
                {
                    if (x[i] > MedianValue)
                        list.Insert(ReturnIndex(x[i], MedianIndex, list.Count - 1), x[i]);
                    else
                        list.Insert(ReturnIndex(x[i], 0, MedianIndex), x[i]);

                }

                count++;
                PrintMedian();
            }
            else
            {
                int index = -1;
                if (count > 0)
                {
                    if (x[i] > MedianValue)
                    {
                        index = list.BinarySearch(MedianIndex, count - MedianIndex, x[i], null);
                    }
                    else
                    {
                        index = list.BinarySearch(0, MedianIndex + 1, x[i], null);
                    }
                }
                if (index < 0)
                    Console.WriteLine("Wrong!");
                else
                {
                    if (x[i] == min)
                        list.RemoveAt(0);
                    else if (x[i] == max)
                        list.RemoveAt(count - 1);
                    else
                    {
                        list.RemoveAt(index);
                    }
                    count--;
                    if (count == 0)
                    {
                        min = long.MaxValue;
                        max = long.MinValue;
                        Console.WriteLine("Wrong!");
                    }
                    else
                        PrintMedian();
                }

            }

        }
        Console.ReadKey();

    }
    private static int ReturnIndex(int item, int start, int end)
    {
        int i = start;
        int j = end;
        while (i <= j)
        {
            int midindex = (i + j) / 2;
            if (item > list[midindex])
            {
                i = midindex + 1;
            }
            else if (item < list[midindex])
                j = midindex - 1;
            else
            {
                return midindex;
            }
        }
        return i;
    }
    private static void PrintMedian()
    {

        if (count == 1)
        {
            MedianIndex = 0;
            MedianValue = list[0];
            min = list[0];
            max = list[0];
            Console.WriteLine(list[0]);
        }
        else
        {
            mid = count / 2;
            MedianIndex = mid;
            MedianValue = list[mid];
            if (count % 2 != 0)
                Console.WriteLine(list[mid]);
            else
            {
                sum = (long)list[mid] + list[mid - 1];
                if (sum % 2 == 0)
                {
                    Console.WriteLine(sum / 2);
                }
                else
                    Console.WriteLine(((double)sum) / 2);
            }
        }
    }
}