qwewqewqqeweqweqw

#include <iostream>
#include <chrono>
#include <vector>
#include <string>
using namespace std;
using namespace std::chrono;

int bruteForce (const vector<int>& input){
    int n = input.size();
    int count = 0;
    for (int i = 0; i<n-1; i++){
        for (int j = i+1; j<n; j++){
            if (input[i] > input[j]){
                count++;
            }
        }
    }
    return count;
}

void Merge(vector<int>& input, int& first, int& last, int& splitInv){
    int middle, start, final;

    int* tmp = new int[last-first];
    middle=(first+last)/2;
    start=first;
    final=middle+1;
    for(int j=0; j<=last-first; j++){
        if ((start<=middle) && ((final>last) || (input[start]<input[final])))   {
            tmp[j]=input[start];
            start++;
        }
        else
        {
            tmp[j]=input[final];
            final++;
            splitInv+=middle+1-start;
        }
    }
    for (int j=0; j<=last-first; j++) {

        input[j+first]=tmp[j];
    }
}

void MergeSort(vector<int>& input, int first, int last, int& splitInv){
    {
        if (first<last){
            MergeSort(input, first, (first+last)/2, splitInv);
            MergeSort(input, (first+last)/2+1, last, splitInv);
            Merge(input, first, last, splitInv);
        }
    }
}

int divideEtImpera(vector<int>& input){
    int splitInv = 0;
    MergeSort(input, 0, input.size()-1, splitInv);
    return splitInv;
}

int main ()
{
    vector<int> something2= {51, 35, 106, 113, 206, 101, 22, 242, 132, 134, 248, 142, 49, 4, 238, 76, 94, 158, 167, 140, 124, 155, 225, 138, 207, 154, 202, 26, 164, 116, 171, 91, 33, 103, 15, 68, 44, 185, 169, 108, 160, 57, 205, 197, 85, 5, 54, 128, 10, 222, 130, 250, 70, 135, 18, 20, 218, 195, 180, 188, 97, 240, 112, 212, 109, 52, 60, 183, 111, 200, 174, 119, 243, 69, 177, 71, 166, 176, 38, 87, 172, 77, 247, 122, 170, 53, 84, 181, 245, 8, 147, 17, 237, 12, 121, 28, 36, 178, 47, 75, 1, 11, 241, 210, 32, 115, 56, 163, 221, 50, 62, 24, 82, 198, 246, 162, 208, 23, 223, 63, 196, 27, 16, 105, 152, 79, 149, 227, 217, 139, 201, 3, 236, 157, 233, 107, 136, 127, 42, 216, 43, 30, 55, 175, 230, 209, 64, 146, 220, 46, 125, 161, 239, 78, 226, 131, 151, 141, 66, 173, 93, 72, 159, 235, 45};
    vector<int> something = {4171, 9166, 9257, 6105, 6885, 5632, 1534, 6089, 7285, 1858, 3711, 1253, 2054, 7717, 1543, 4215, 1627, 9466, 1834, 7727, 6803, 7195, 4469, 6086, 3447, 8873, 1980, 6222, 2134, 5530, 1157, 6304, 4697, 414, 2410, 1582, 6046, 3944, 7670, 3331, 5801, 1381, 4583, 7854, 9098, 6126, 2070, 725, 5592, 3904, 8452, 2395, 1099, 2921, 8481, 4545, 1794, 462, 768, 3928, 5991, 1924, 232, 689, 2338, 2642, 2270, 8383, 6585, 9940, 1715, 2387, 1321, 6298, 242, 420, 2424, 2312, 1144, 8015, 6215, 9595, 411, 7314, 2517, 8891, 1859, 4311, 9353, 2626, 8238, 5345, 4550, 8470, 6033, 6888, 1112, 8303, 5272, 7696, 8243, 6986, 83, 9564, 3285, 325, 9983, 5708, 2636, 1127, 3723, 8850, 722, 4133, 6164, 3239, 3025, 8023, 7549, 2378, 650, 5787, 7723, 5200, 4258, 3756, 2088, 5369, 2059, 7360, 3066, 302, 4347, 3149, 9866, 7631, 3473, 9849, 3339, 6108, 976, 7061, 4959, 1698, 1194, 1123, 4936, 4219, 9146, 2486, 6596, 9795, 8273, 4320, 4996, 2531, 8075, 7084, 7899, 135, 4444, 966, 437, 8791, 4114, 303, 6422, 7586, 152, 9761, 3695, 1128, 6822, 8653, 2825, 8016, 9775, 7761, 2235, 8922, 247, 8831, 8718, 8520, 3151, 3714, 1051, 1227, 798, 8950, 1362, 5242, 9915, 1798, 4033, 4029, 2101, 455, 1616, 2253, 216, 5310, 3380, 7038, 3963, 6205, 5055, 3739, 3967, 7289, 2661, 4214, 6121, 1379, 2734, 9271, 5093, 3784, 498, 5891, 2735, 1860, 1133, 2650, 3657, 5165, 6678, 5758, 5620, 8293, 8010, 5836, 3604, 1391, 2874, 7566, 7596, 7928, 1305, 1563, 5218, 3966, 5777, 1340, 8511, 611, 438, 2296, 1109, 6328, 5030, 2968, 7461, 7679, 6625, 4358, 2383, 8245, 2652, 394, 4082, 6255, 1785, 6955, 3821, 9380, 4884, 5126, 944, 103, 9092, 6720, 1442, 4437, 5232, 2053, 4875, 7527, 3162, 1204, 2557, 6129, 8665, 236, 2755, 1291, 4593, 5138, 9536, 7245, 5531, 3618, 3500, 7316, 574, 7321, 6696, 5458, 2448, 7640, 5560, 1540, 4360, 7002, 5977, 9592, 9055, 853, 7119, 2217, 2057, 9675, 8346, 9911, 1101, 2013, 4505, 6239, 1549, 1750, 1770, 5167, 5249, 9085, 5740, 2571, 5782, 1199, 5018, 3422, 6759, 6557, 7782, 3761, 2535, 7374, 2816, 3387, 4494, 5033, 5443, 4169, 3379, 6165, 4081, 4479, 8177, 8585, 718, 9726, 336, 2488, 4893, 5584, 1574, 634, 8155, 7356, 1832, 3173, 778, 8590, 9730, 8560, 2352, 2265, 5935, 5168, 5652, 429, 201, 1095, 4598, 3579, 7260, 8678, 8058, 5437, 7263, 8776, 5163, 7599, 1265, 57, 3183, 2839, 691, 1339, 195, 2522, 4511, 973, 1113, 4241, 9533, 3465, 6506, 5468, 8632, 2158, 5896, 8833, 3253, 494, 2413, 513, 9171, 472, 5950, 6435, 9247, 4034, 1170, 7217, 3351, 8556, 3546, 4382, 3067, 4519, 5495, 7308, 4052, 8959, 3814, 9519, 7592, 5971, 5416, 6426, 9223, 5910, 8838, 9735, 5082, 9309, 5686, 1518, 8557, 6799, 5552, 9070, 7968, 2769, 2422, 9828, 1325, 5967, 4210, 4392, 487, 9704, 1700, 4538, 8664, 5513, 4058, 6256, 1485, 9474, 2682, 708, 5384, 1521, 444, 466, 831, 1983, 9387, 2928, 7534, 8458, 897, 304, 880, 1629, 6847, 4934, 6020, 7333, 4639, 7720, 1872, 3303, 3234, 5929, 9558, 4718, 5403, 2241, 5426, 788, 5870, 4591, 1999, 3236, 3979, 4927, 770, 2437, 5824, 1074, 3317, 6548, 2702, 165, 1483, 8722, 7497, 6443, 9369, 9424, 9676, 5299, 8983, 4395, 702, 1224, 9820, 1490, 4985, 5690, 2742, 9576, 7689, 3555, 2617, 6747, 5992, 8440, 7821, 4988, 523, 9473, 6471, 9245, 6971, 2592, 5689, 6340, 2017, 5365, 1639, 1000, 9760, 2341, 2224, 9580, 3830, 7208, 5271, 6572, 6784, 2961, 2550, 340, 5578, 9297, 6332, 4018, 7118, 5641, 9006, 7641, 5115, 5477, 6886, 2086, 8069, 2575, 8425, 86, 7940, 65, 1086, 7701, 2405, 3309, 7282, 6235, 517, 2553, 2807, 7301, 5514, 5357, 1092, 4654, 3973, 5110, 1772, 9614, 4116, 9412, 4729, 6299, 6815, 7662, 8874, 5241, 7748, 5305, 4516, 7710, 2142, 3945, 2659, 4350, 6752, 9960, 9864, 2109, 7601, 957, 6762, 1575, 6066, 8533, 1189, 182, 7946, 5918, 9774, 4245, 2733, 7436, 3119, 7973, 5185, 9933, 3278, 4449, 989, 6160, 6246, 8819, 597, 1686, 8779, 3795, 6381, 1418, 557, 7955, 7483, 9090, 9144, 7665, 7037, 5062, 7439, 1282, 7794, 4876, 4401, 5768, 61, 4335, 9046, 4079, 8784, 35, 239, 5031, 4968, 9058, 5628, 6654, 7837, 6090, 449, 4218, 7507, 1006, 2174, 4991, 96, 1318, 2656, 7133, 6380, 95, 8415, 4174, 4971, 9942, 7151, 8988, 9110, 5936, 9022, 9349, 967, 3991, 8407, 6595, 645, 6244, 2685, 1093, 463, 193, 2098, 2637, 5183, 2194, 3955, 7838, 9326, 335, 7932, 7741, 4509, 2904, 558, 4451, 7934, 7709, 3439, 7045, 3645, 2461, 6394, 4612, 6451, 4801, 1208, 7095, 1046, 3892, 8188, 1509, 4084, 286, 4146, 9266, 2480, 8100, 7104, 1807, 8434, 5037, 9547, 2943, 106, 7393, 5875, 7815, 833, 1460, 3293, 9314, 6072, 9744, 7279, 6840, 5162, 1172, 5028, 6671, 5255, 5314, 817, 4522, 7793, 8916, 9599, 7351, 6663, 9147, 295, 4604, 9253, 7688, 480, 7068, 3400, 8528, 1813, 2715, 4601, 1558, 6830, 1880, 8398, 1993, 3051, 3426, 8663, 8306, 8740, 9480, 2828, 6534, 8397, 4455, 6134, 5749, 1118, 5281, 6043, 5722, 4535, 3731, 6202, 1604, 2251, 9601, 132, 4064, 2316, 4732, 5621, 6612, 4019, 1140, 9663, 7445, 9803, 7969, 6186, 9283, 2720, 7681, 5252, 8853, 3430, 6370, 4135, 2093, 8669, 3204, 8294, 273, 5454, 7896, 405, 9518, 213, 5137, 5140, 9359, 1749, 9159, 499, 1412, 6604, 9381, 2791, 9586, 180, 5510, 7267, 5432, 4363, 698, 1803, 8497, 171, 3895, 7167, 3374, 2190, 7440, 8828, 7844, 8347, 299, 2981, 3487, 9657, 2646, 157, 6141, 9250, 459, 5523, 2042, 45, 5703, 7551, 7311, 1135, 1914, 8008, 2937, 412, 8179, 6831, 7579, 1554, 9021, 5019, 383, 9106, 2863, 8729, 9404, 5843, 9062, 573, 4863, 9218, 6714, 2238, 6155, 9720, 3706, 7032, 9074, 5041, 2011, 6032, 3220, 8842, 3611, 4773, 7864, 8629, 5156, 6970, 1493, 3885, 6375, 7336, 6102, 5438, 7909, 965, 4656, 4623, 5078, 4332, 6860, 1233, 4053, 4800, 4939, 1085, 3875, 560, 6125, 5886, 6591, 9344, 4728, 202, 4118, 9273, 9562, 3159, 5938, 7660, 9260, 1376, 5569, 226, 5303, 365, 7052, 6536, 4417, 1853, 1475, 5501, 5728, 2035, 1614, 8625, 972, 6342, 8827, 5089, 8933, 7659, 8496, 7983, 7522, 4435, 5643, 6782, 5811, 1213, 7007, 1843, 1405, 2311, 2208, 8457, 8846, 6624, 311, 322, 2126, 6038, 2356, 3753, 7651, 982};

    auto start1 = steady_clock::now ();
    cout << bruteForce(something) << endl;
    auto finish1 = steady_clock::now ();
    cout<< "bruteForce "<< duration_cast<milliseconds> (finish1 - start1).count () << " ms" << endl;

    auto start2 = steady_clock::now ();
    cout << divideEtImpera(something) << endl;
    auto finish2 = steady_clock::now ();
    cout<< "divideEtImpera "<< duration_cast<milliseconds> (finish2 - start2).count () << " ms" << endl;

    system("pause");
}