#include <iostream>
#include <vector>
#include <string>

using namespace std;

long long getTotalPalindromeTransformationCost(const string& s) {
    int mask = 0;
    int n = s.length();
    vector<int> f(26, 0);
    long long ans = 0;

    for (int i = 0; i < n; i++) {
        mask ^= 1 << (s[i] - 'a'); 
        int cnt = 0;

        for (int j = 0; j < 26; j++) {
            if (mask & (1 << j)) {
                cnt += i + 1 - f[j];
                f[j] += 1; 
            } else {
                cnt += f[j]; 
            }
        }

        ans += (cnt - (i + 2) / 2) / 2;
    }

    return ans;
}

#include <bits/stdc++.h>
using namespace std;
long long binomialCoeff(int n, int k) {
    long long res = 1;
    if (k > n - k)
        k = n - k;

    for (int i = 0; i < k; ++i) {
        res *= (n - i);
        res /= (i + 1);
    }

    return res;
}

long long catalanNumber(int k) {
    long long c = binomialCoeff(2 * k, k);
    return c / (k + 1);
}

int main() {
    int n;
    cin >> n;

    long long result = catalanNumber(n - 1);
    
    cout << result << endl;

    return 0;
}

#include<iostream>
using namespace std;
int t,a[200010],n,k;
int main(){
cin>>t;
while(t--){
  cin>>n>>k;
  int l=1,r=n;
  for(int j=1;j<=k;j++){
   for(int i=j;i<=n;i+=k){
    if(i&1)a[i]=l++;
    else a[i]=r--;
   }
  }
  for(int i=1;i<=n;i++){
   cout<<a[i]<<" ";
  }
  cout<<endl;
}

return 0;
}

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int ss(int n, vector<int>& arr) {
    unordered_map<int, int> frequency;
        for (int num : arr) {
        frequency[num]++;
    }
    
    int odd_count = 0;
    
    for (auto& pair : frequency) {
        if (pair.second % 2 != 0) {
            odd_count++;
        }
    }
    
    return odd_count / 2;
}

int main() {
    int N;
    cin >> N;
    
    vector<int> arr(N);
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    
    int result = ss(N, arr);
    cout << result << endl;

    return 0;
}

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
void computeSums(const vector<int>& a, vector<int>& b, int c, int d) {
    if (c == a.size()) {
        b.push_back(d);
        return;
    }

    computeSums(a, b, c + 1, d + a[c]);
    computeSums(a, b, c + 1, d);
}

int main() {
    int e, f;
    cin >> e;

    cin >> f;

    vector<int> g(e);
    for (int h = 0; h < e; h++) {
        cin >> g[h];
    }

    vector<int> i, j;
    computeSums(vector<int>(g.begin(), g.begin() + e / 2), i, 0, 0);
    computeSums(vector<int>(g.begin() + e / 2, g.end()), j, 0, 0);

    unordered_set<int> k(i.begin(), i.end());

    for (int l : j) {
        if (k.count(f - l)) {
            cout << 1 << endl;
            return 0;
        }
    }

    cout << 0 << endl;
    return 0;
}

#include <iostream>
#include <bitset>
using namespace std;

bool isPow2Minus1(int n) {
    return (n & (n + 1)) == 0;
}

int maxSplitAnd(int num) {
    string b = bitset<32>(num).to_string(); 
    int m = b.find('1'); 
    b = b.substr(m); 
    int maxRes = -1;

    for (int i = 1; i < b.length(); i++) {
        int p1 = stoi(b.substr(0, i), nullptr, 2);
        int p2 = stoi(b.substr(i), nullptr, 2);
        int res = p1 & p2;
        if (isPow2Minus1(res)) {
            maxRes = max(maxRes, res);
        }
    }
    return maxRes;
}

int main() {
    int n;
    cin >> n;
    cout << maxSplitAnd(n) << endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int find(int *p, int i) {
    if (p[i] == i) return i;
    return find(p, p[i]);
}

void unionSets(int *p, int *r, int x, int y) {
    int xr = find(p, x);
    int yr = find(p, y);
    if (r[xr] < r[yr]) p[xr] = yr;
    else if (r[xr] > r[yr]) p[yr] = xr;
    else {
        p[yr] = xr;
        r[xr]++;
    }
}

int kruskal(int n, vector<tuple<int, int, int>> &edges, bool mx) {
    int p[n], r[n], cost = 0, cnt = 0;
    for (int i = 0; i < n; i++) {
        p[i] = i;
        r[i] = 0;
    }
    sort(edges.begin(), edges.end(), mx {
        return mx ? get<2>(a) > get<2>(b) : get<2>(a) < get<2>(b);
    });
    for (auto &e : edges) {
        int u = get<0>(e), v = get<1>(e), c = get<2>(e);
        if (find(p, u) != find(p, v)) {
            cost += c;
            cnt++;
            unionSets(p, r, u, v);
            if (cnt == n - 1) break;
        }
    }
    return cost;
}

pair<int, int> minMaxCost(int n, vector<int> &h) {
    vector<tuple<int, int, int>> edges;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            edges.emplace_back(i, j, abs(h[i] - h[j]));
        }
    }
    return {kruskal(n, edges, false), kruskal(n, edges, true)};
}

int main() {
    int n;
    cin >> n;
    vector<int> h(n);
    for (int i = 0; i < n; i++) cin >> h[i];
    auto res = minMaxCost(n, h);
    cout << res.first << " " << res.second << endl;
    return 0;
}