#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1e5 + 10;
int a[N],n;
int main(void)
{
    cin>>n;
    for(int i = 1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    int mid = a[n/2 + 1];
    long long ans = 0;
    for(int i = 1;i<=n;i++)  ans += abs(a[i] - mid);
    cout<<ans<<endl;
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 550;
int dp[N][N],n,a[N][N];

int main(void)
{
    cin>>n;
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=i;j++) cin>>a[i][j];

    memset(dp,0xcf,sizeof dp);
    for(int j = 1;j<=n;j++) dp[n][j] = a[n][j];
    for(int i = n-1;i>=1;i--)
        for(int j = 1;j<=i;j++) dp[i][j] = max(dp[i+1][j] + a[i][j],dp[i+1][j+1] + a[i][j]);
    cout<<dp[1][1]<<endl;
    return 0;
}

//时间复杂度为O(n^3)
//基于动态规划思想
//状态表示：d[k][i][j]表示经过前k个点从i到达j的最短距离
//阶段划分：经过前k个点
//转移方程：d[k][i][j] = min(d[k-1][i][k] + d[k-1][k][j],d[k][i][j])
//初始化：根据题目来
//目标：d[k][i][j];
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 2e2 + 10,INF = 0x3f3f3f3f;
int d[N][N],n,m,q;
void floyd()
{
    for(int k = 1;k<=n;k++)
        for(int i = 1;i<=n;i++)
            for(int j = 1;j<=n;j++) d[i][j] = min(d[i][j],d[i][k] + d[k][j]);
}
int main(void)
{
    cin>>n>>m>>q;
    for(int i = 1;i<=n;i++) 
        for(int j = 1;j<=n;j++)
        if(i == j) d[i][j] = 0;
        else d[i][j] = INF;

    while(m--)
    {
        int a, b, c;
        cin>>a>>b>>c;
        d[a][b] = min(d[a][b],c);
    }

    floyd();

    while(q--)
    {
        int a,b;
        cin>>a>>b;
        if(d[a][b] > INF / 2) puts("impossible");//因为存在负边可能会导致其小于INF
        else cout<<d[a][b]<<endl;
    }
    return 0;
}

//时间复杂度为O(n ^ 2)
//裸dijkstra
//广播问题：求解起始点到达所有点的最短距离的最大值，当最大的遍历到了，其余的点也就遍历到了
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
int n,m;
const int N = 1e2 + 10,M = 4e2 + 10;
int h[N],e[M],ne[M],w[M],idx,dist[N];
bool st[N];
void dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;

    for(int i = 1;i<=n;i++)
    {
        int t = -1;
        for(int j = 1;j<=n;j++)
        if(!st[j] && (t == -1 || dist[t] > dist[j])) t = j;

        st[t] = true;

        for(int ix = h[t];~ix;ix = ne[ix])
        {
            int j = e[ix],c = w[ix];
            if(!st[j]) dist[j] = min(dist[j],dist[t] + c);
        }
    }

}
void add(int a,int b,int c)
{
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}
int main(void)
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i = 1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    dijkstra();
    int time = 0;
    for(int i = 1;i<=n;i++)
        time = max(dist[i],time);

    if(time == 0x3f3f3f3f) cout<<-1<<endl;
    else cout<<time<<endl;
    return 0;
}

//时间复杂度为O(n ^ 2)
//裸dijkstra
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
int n,C,S,E;
const int N = 3e3 + 10,M = 2e4 + 10;
int h[N],e[M],ne[M],w[M],idx,dist[N];
bool st[N];
int dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    dist[S] = 0;

    for(int i = 1;i<=n;i++)
    {
        int t = -1;
        for(int j = 1;j<=n;j++)
        if(!st[j] && (t == -1 || dist[t] > dist[j])) t = j;

        st[t] = true;

        for(int ix = h[t];~ix;ix = ne[ix])
        {
            int j = e[ix],c = w[ix];
            if(!st[j]) dist[j] = min(dist[j],dist[t] + c);
        }
    }
    return dist[E];
}
void add(int a,int b,int c)
{
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}
int main(void)
{
    cin>>n>>C>>S>>E;
    memset(h,-1,sizeof h);
    for(int i = 1;i<=C;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }

    cout<<dijkstra()<<endl;
    return 0;
}

//思路：时间复杂度为O(n^2)
//并查集求连通块的个数
//暴力枚举每个节点求最大深度
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 1e4 + 10;
int p[N],n,depth;
vector<pair<int,int> > node;//存储叶子节点
int cnt[N],h[N],ne[N],e[N],idx;
bool st[N];
int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}
void dfs(int u,int dep)
{
    depth = max(dep,depth);
    st[u] = true;
    for(int i = h[u];~i;i=ne[i]) 
    {
        int j = e[i];
        if(st[j]) continue;
        dfs(j,dep + 1);
    }
}
bool cmp(pair<int,int> a,pair<int,int>  b)
{
    if(a.first != b.first) return a.first < b.first;
    return a.second > b.second;
}

void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
int main(void)
{
    memset(h,-1,sizeof h);
    cin>>n;
    for(int i = 1;i<=n;i++) p[i] = i;
    for(int i = 1;i<n;i++) 
    {
        int a,b;
        cin>>a>>b;
        int pa = find(a),pb = find(b);
        if(pa != pb) p[pb] = pa;
        add(a,b);add(b,a);
    }

    int total = 0;
    for(int i = 1;i<=n;i++) if(p[i] == i) total ++;

    if(total > 1) printf("Error: %d components\n",total);
    else 
    {

        for(int i = 1;i<=n;i++)
        {
            memset(st,false,sizeof st);
            depth = 1;
            dfs(i,1);
            node.push_back(make_pair(depth,i));
        }

        sort(node.begin(),node.end(),cmp);

        int dept = node[node.size()-1].first;
        for(int i = node.size() - 1;i>=0;i--) 
        if(node[i].first == dept) cout<<node[i].second<<endl;
        else break;
    }
    return 0;
}

//时间复杂度为O(n)
//反思：若通过前序遍历和中序遍历如何确定一棵树呢？
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;
const int N = 40;
unordered_map<int,int> l,r,pos;//pos存储的是在中序遍历中每个节点在序列位置的映射，如1,2,3,5,6 pos[5] = 4
int postorder[N],inorder[N],path[N];
int n;
int build(int il,int ir,int pl,int pr)//il,ir为该树在中序遍历的区间，pl,pr为该树在后序遍历的区间
{
    int root = postorder[pr];//树的根节点可以在后序遍历中找到
    int k = pos[root];//找到这个根节点在中序遍历中的位置，以此来划分区间

    if(il < k) l[root] = build(il,k-1,pl,pl + k - 1 - il);//若该节点有左子树，则该树在中序遍历中为il,k-1，后序遍历直接通过树中节点个数相等
    if(k < ir) r[root] = build(k+1,ir,pr+k-ir,pr-1);

    return root;
}
void bfs(int root)
{
    queue<int> q;
    q.push(root);
    int cnt = 0;
    while(q.size())
    {
        int t = q.front();
        q.pop();
        path[++cnt] = t;
        if(l.count(t)) q.push(l[t]);
        if(r.count(t)) q.push(r[t]);
    }

    cout<<path[1];
    for(int i = 2;i<=n;i++) cout<<' '<<path[i];
    cout<<endl;
}
int main(void)
{
    cin>>n;
    for(int i = 1;i<=n;i++) cin>>postorder[i];
    for(int i = 1;i<=n;i++) 
    {
        cin>>inorder[i];
        pos[inorder[i]] = i;
    }

    int root = build(1,n,1,n);
    bfs(root);
    return 0;
}

//时间复杂度为O(n)每个节点只会被遍历一次
//搜索框架：对于当前访问到的节点，搜索分支为与其相邻的边，(u,depth)
//cnt[depth]存储的是depth层的叶子节点个数
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
int n, m;
const int N = 1e2 + 10;
int h[N],ne[N],e[N],idx = 0,cnt[N],d;
void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}

void dfs(int u,int depth)//因为是一棵树且边都是有向边，不存在自环，故不需要判定每一个节点只走过一次
{
    d = max(d,depth);
    if(h[u] == -1)
    {
        cnt[depth]++;
        return ;
    }
    for(int i = h[u];~i;i = ne[i])
    {
        int j = e[i];
        dfs(j,depth + 1);
    }
}
int main(void)
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    for(int i = 1;i<=m;i++)
    {
        int id,k;
        cin>>id>>k;
        while(k --)
        {
            int b;
            cin>>b;
            add(id,b);
        }
    }
    dfs(1,1);
    for(int i = 1;i<=d;i++) cout<<cnt[i]<<' ';
    cout<<endl;
    return 0;
}

//时间复杂度为O(n ^ 2)
//思路：dijkstra算法在松弛的那一步进行更新操作
//sum[j]存的时到j点的最短路径的最小花费，map[j]存的时到达j的最短路径且花费最小的j的前一个点

//设t为当前刚加入S的点，即t为刚确定的距离start最短距离确定点
//在松弛操作时,对于点j进行松弛
//若s-->t-->j路径唯一即 dist[j] > dist[t] + g[t][j]
//那么map[j] = t,sum[j] = sum[t] + w[t][j];
//若s-->t-->j路径不唯一即有 dist[j] == dist[t] + g[t][j],这说明之前必然有一点a使得
//s-->a-->j使得dist[j] == dist[a] + g[a][j]
//那么我们存取sum[t] + w[t][j]较小者(根据题意)
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 5e2 + 10;
int n, m, S, D;
int g[N][N],w[N][N],map[N],sum[N],dist[N];
bool st[N];
void print(int x)
{
    if(x == S) return;
    x = map[x];
    print(x);
    cout<<x<<' ';
}
void dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    dist[S] = 0;
    for(int i = 0;i<n;i++)
    {
        int t = -1;
        for(int j = 0;j<n;j++) 
        if(!st[j] && (t == -1 || dist[j] < dist[t])) t = j;

        st[t] = true;
        for(int j = 0;j<n;j++)
        if(dist[j] > dist[t] + g[t][j])
        {
            dist[j] = dist[t] + g[t][j];
            sum[j] = sum[t] + w[t][j];
            map[j] = t;
        }
        else if(dist[j] == dist[t] + g[t][j] && (sum[j] > sum[t] + w[t][j]))
        {
            map[j] = t;
            sum[j] = sum[t] + w[t][j];
        }
    }
}
int main(void)
{
    cin>>n>>m>>S>>D;

    memset(g,0x3f,sizeof g);
    for(int i = 0;i<m;i++)
    {
        int a,b,c,cost;
        cin>>a>>b>>c>>cost;
        g[a][b] = g[b][a] = min(g[a][b],c);
        w[a][b] = w[b][a] = cost;
    }
    dijkstra();
    print(D);
    cout<<D<<' '<<dist[D]<<' '<<sum[D]<<endl;
    return 0;
}

//时间复杂度为O(n ^ 2)
//思路：dijkstra算法在松弛的那一步进行更新操作
//sum[j]存的时到j点的最短路径的最小花费，map[j]存的时到达j的最短路径且花费最小的j的前一个点

//设t为当前刚加入S的点，即t为刚确定的距离start最短距离确定点
//在松弛操作时,对于点j进行松弛
//若s-->t-->j路径唯一即 dist[j] > dist[t] + g[t][j]
//那么map[j] = t,sum[j] = sum[t] + w[t][j];
//若s-->t-->j路径不唯一即有 dist[j] == dist[t] + g[t][j],这说明之前必然有一点a使得
//s-->a-->j使得dist[j] == dist[a] + g[a][j]
//那么我们存取sum[t] + w[t][j]较小者(根据题意)
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 5e2 + 10;
int n, m, S, D;
int g[N][N],w[N][N],map[N],sum[N],dist[N];
bool st[N];
void print(int x)
{
    if(x == S) return;
    x = map[x];
    print(x);
    cout<<x<<' ';
}
void dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    dist[S] = 0;
    for(int i = 0;i<n;i++)
    {
        int t = -1;
        for(int j = 0;j<n;j++) 
        if(!st[j] && (t == -1 || dist[j] < dist[t])) t = j;

        st[t] = true;
        for(int j = 0;j<n;j++)
        if(dist[j] > dist[t] + g[t][j])
        {
            dist[j] = dist[t] + g[t][j];
            sum[j] = sum[t] + w[t][j];
            map[j] = t;
        }
        else if(dist[j] == dist[t] + g[t][j] && (sum[j] > sum[t] + w[t][j]))
        {
            map[j] = t;
            sum[j] = sum[t] + w[t][j];
        }
    }
}
int main(void)
{
    cin>>n>>m>>S>>D;

    memset(g,0x3f,sizeof g);
    for(int i = 0;i<m;i++)
    {
        int a,b,c,cost;
        cin>>a>>b>>c>>cost;
        g[a][b] = g[b][a] = min(g[a][b],c);
        w[a][b] = w[b][a] = cost;
    }
    dijkstra();
    print(D);
    cout<<D<<' '<<dist[D]<<' '<<sum[D]<<endl;
    return 0;
}