Find The Median in java

The median of a list of numbers is essentially its middle element after sorting. The same number of elements occur after it as before. Given a list of numbers with an odd number of elements, find the median.

Input

The first line inputs integer n, size of array a.
The second line inputs n space-seperated integers, i.e., a[i].

Constraints:

1 <= n <= 1000001
n is odd
-10000 <= a[i] <= 10000

Output

In a new line, print the median of the array.

Example

Input:

7
0 1 2 4 6 5 3

Output:

3

Explanation:

The sorted a=[0,1,2,3,4,5,6].
Its middle element is at a[3]=3.

Solution of Find The Median in java:–

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		//your code here
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();

      int arr[] = new int[n];

      for(int i=0;i<n;i++)
        {
          arr[i]=sc.nextInt();
        }

      for(int i=0;i<n;i++)
        {
          for(int j=0;j<n;j++)
            {
              int temp=0;
              if(arr[i]>arr[j])
              {
                temp=arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
              }
            }
        }
      System.out.println(arr[n/2]);
      
	}
}