#include <iostream>
#include <algorithm> // For sort
using namespace std;

// Generic function to calculate the median
template <class T>
T CalculateMedian(T arr[], int size) {
    // Sort the array
    sort(arr, arr + size);

    // If the size is odd, return the middle element
    if (size % 2 != 0) {
        return arr[size / 2];
    } 
    // If the size is even, return the average of the two middle elements
    else {
        return (arr[(size / 2) - 1] + arr[size / 2]) / 2.0;
    }
}

int main() {
    // Test with integers
    int intArr[] = {10, 2, 5, 8, 1};
    int intSize = sizeof(intArr) / sizeof(intArr[0]);
    cout << "Median (int): " << CalculateMedian(intArr, intSize) << endl;

    // Test with floating-point values
    double doubleArr[] = {2.5, 1.0, 3.5, 4.0, 6.0};
    int doubleSize = sizeof(doubleArr) / sizeof(doubleArr[0]);
    cout << "Median (double): " << CalculateMedian(doubleArr, doubleSize) << endl;

    // Test with characters
    char charArr[] = {'z', 'a', 'g', 'm', 'b'};
    int charSize = sizeof(charArr) / sizeof(charArr[0]);
    cout << "Median (char): " << CalculateMedian(charArr, charSize) << endl;

    return 0;
}