int flatlandSpaceStations(int n, vector<int> c) {
    sort(c.begin(), c.end());
    int result = c[0];
    for(int i = 1; i < c.size(); i++){
        result = max(result, (c[i] - c[i-1]) / 2 );
    }
    result = max(result, n - 1 - c[c.size() - 1]);
    return result;
}

    sort(c.begin(), c.end());

    c = countingtSort(c, n);

vector<int> countingtSort(vector<int>c, int n) {
    vector<int> arr(n, 0), result;
    for(auto el: c) arr[el] = 1;
    for(int i = 0; i < n; i++) if(arr[i]) result.push_back(i);
    return result;
}

def flatlandSpaceStations(n, c, m):
    c.sort()
    maxi=max(abs(c[0]-0),abs((n-1)-c[-1]))
    if n<=m:
        return '0'
    for i in range(m-1):
        maxi=max(abs(c[i]-c[i+1])//2,maxi)
    return maxi

// Complete the flatlandSpaceStations function below.
    static int flatlandSpaceStations(int n, int[] c) {

    	int numberOfCities = n;
    	int numberOfStations = c.length;
    	
    	// Each city can have one station. If numberOfCities == numberOfStations. Each city has station so distance will be 0
    	if (numberOfCities == numberOfStations) {
    		return 0;
    	}
    	
    	// If there is only station subtract 1 from numberOfCities
    	if (numberOfStations == 1) {
    		return numberOfCities - 1;
    	}
    	
    	/**
    	 * By default Priority queue gives priority to smaller elements. By using priority Queue we will be sure that we will always get the station in the 
    	 * same order as we are traversing the cities.
    	 * 
    	 * Suppose stations are given in order [4, 7, 1]. We will start iterating from city 0. City 0 till city 4 should check distance with spaceStationCity 1
    	 * and spaceStationCity 4.
    	 * 
    	 * After passing spaceStationCity 4 cities should check distance with spaceStationCity 4 and spaceStationCity 7.
    	 */
    	PriorityQueue<Integer> spaceStationsCityPriorityQueue = new PriorityQueue<>();
    	for (int spaceStationCity : c) {
    		spaceStationsCityPriorityQueue.add(spaceStationCity);
    	}
    	
    	// At this point we know that there are atl-east 2 space stations
    	int spaceStationCity1 = spaceStationsCityPriorityQueue.poll();
    	int spaceStationCity2 = spaceStationsCityPriorityQueue.poll();
    	
    	// We can also use max variable and check it instead of creating the array. But let's do it with array as questions is also showing the array.
    	int[] distanceArr = new int[n];
    	
    	/**
    	 * 
    	 * We have taken the first two stations. We are using priority queue. We know we will get the stations in order.
    	 * Start from city 0.
    	 * Check the city distance from space station 1 and space station 2.
    	 * Find the minimum of both distance.
    	 * Add minimum distance to distance array.
    	 * Once the space station city 2 reaches. Now change the space station city 
    	 * 
    	 */
    	for (int i = 0; i < numberOfCities; i++ ) {
    		
    		int city = i;
    		int spaceStationCity1Distance = Math.abs(city - spaceStationCity1); 
    		int spaceStationCity2Distance = Math.abs(city - spaceStationCity2); 
    		
    		int minSpaceStationDistance = Math.min(spaceStationCity1Distance, spaceStationCity2Distance);
    		distanceArr[i] = minSpaceStationDistance;
    		
    		if (city == spaceStationCity2) {
    			spaceStationCity1 = spaceStationCity2;
    			if (spaceStationsCityPriorityQueue.isEmpty()) {
    				spaceStationCity2 = 0;
    			} else {
    				spaceStationCity2 = spaceStationsCityPriorityQueue.poll();
    			}
    			
    		}
    		
    	}
    	
    	int maxDistance = findMax(distanceArr);
    	return maxDistance;
    
    }
    
    public static int findMax(int[] arr) {
    	
    	int max = Integer.MIN_VALUE;
    	
    	for (int number : arr) {
    		if (number > max) {
    			max = number;
    		}
    	}
    	
    	return max;
    	
    }

def flatlandSpaceStations(n, c):
  c.sort()
  for i in range(len(c)):
    if i==0:a=c[i]
    if i==len(c)-1:
      a=max(n-1-c[i],a)
      break
    a=max((c[i+1]-c[i])//2,a)
  return a