#include<iostream>
#include<vector>

using namespace std;

// 数据量上升 ->  优化

// 状态表示: 
//  集合: 以第i个数结尾的最大子序列的长度
//  属性: max
//
// 状态计算:
//  集合划分: 根据第i-1个数分类
//      即, 枚举i-1的所有可能情况
//
// 优化: 相同长度的子序列, 只记录结尾最小的那一个
//  因为适用性更高 (贪心)
//
//  利用二分找到小于某个数的最大的数

#define N 100100

int q[N];
int a[N];

int main() {
  int n;
  cin >> n;
  for(int i=0;i<n;i++) cin >> a[i];
  int len = 0;
  q[0] = -2e9;
  for(int i=0;i<n;i++) {
    int l=0, r = len;
    // 利用二分找到小于某个数的最大的数
    while(l < r) {
      int mid = l + r + 1 >> 1;
      if(q[mid] < a[i]) l = mid;
      else r = mid - 1;
    }
    len = max(len, r + 1);
    q[r + 1] = a[i];
  }
  cout << len;
  return 0;
}

#include<iostream>
#include<vector>

using namespace std;

// 状态表示: 
//  集合: 以第i个数结尾的最大子序列的长度
//  属性: max
//
// 状态计算:
//  集合划分: 根据第i-1个数分类
//      即, 枚举i-1的所有可能情况

#define N 1010

int f[N];
int a[N];

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

  for(int i=0;i<n;i++) {
    f[i] = 1;
    for(int j=0;j<i;j++) {
      if(a[j] < a[i])
        f[i] = max(f[i], f[j]+1);
    }
  }
  int ans = 0;
  for(int i=0;i<n;i++) ans = max(ans, f[i]);
  cout << ans;

  return 0;
}

#include<iostream>
#include<climits>

using namespace std;

// n行
// 后续每行i的元素个数为i
// 从一个节点移动到左下或右下
//
// 到达底层的最大路径
//
// 从下到上比较方便, 不用特判

//         7
//       3   8
//     8   1   0
//   2   7   4   4
// 4   5   2   6   5

// 状态表示
//  集合: dp[i][j], i层j列的路径和
//  属性: 最大
//
// 集合划分
//  数组二叉树, 来自左父或右父
//  dp[i][0] = dp[i-1][0]
//  dp[i][j] = max(dp[i-1][j], dp[i-1][j-1])
//  dp[i][i] = dp[i-1][i-1]

// 5
//     7
//    3 8
//   8 1 0 
//  2 7 4 4
// 4 5 2 6 5
#define N 501

int dp[N][N];
int nums[N][N];

int main() {
  int n;

  cin >> n;

  for(int i=0;i<n;i++) {
    for(int j=0;j<=i;j++) { 
      cin >> nums[i][j];
      dp[i][j] = 0;
    }
  }

//  int ans = INT_MIN;
//   for(int i=0;i<n;i++) {
//  for(int j=0;j<=i;j++) { 
//    if(i==0) dp[i][j] = nums[i][j];
//    else if(j==0) dp[i][j] = nums[i][j] + dp[i-1][j];
//    else if(j==i) dp[i][j] = nums[i][j] + dp[i-1][j-1];
//    else dp[i][j] = nums[i][j] + max(dp[i-1][j], dp[i-1][j-1]);
//  }
//   }
// 
//   for(int j=0;j<n;j++) { 
//  ans = max(dp[n-1][j], ans); 
//   }
//  cout << ans;


  // 从下到上, 一次n^2 > n^2 + n
  for(int i=n-1;i>=0;i--) {
    for(int j=0;j<=i;j++) { 
      if(i==n-1) dp[i][j] = nums[i][j];
      // else if(j==0) dp[i][j] = nums[i][j] + dp[i-1][j];
      // else if(j==i) dp[i][j] = nums[i][j] + dp[i-1][j-1];
      else dp[i][j] = nums[i][j] + max(dp[i+1][j], dp[i+1][j+1]);
    }
  }

  cout << dp[0][0];

  return 0;
}

#include<iostream>
#include<vector>

using namespace std;


// 物品组
// dp[i][j] 前i组物品

#define N 110

int v[N], w[N];
int f[N];

int main() {
  int n, m;
  cin >> n >> m;
  for(int i=1;i<=n;i++) {
    int s;
    cin >> s;
    for(int j=0;j<s;j++) cin >> v[j] >> w[j];
    for(int j=m;j>0;j--)
      for(int k=0;k<s;k++)
        if(j >= v[k])
          f[j] = max(f[j], f[j - v[k]] + w[k]);

  }
  cout << f[m];

    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

// 背包数量有限
//
// 算法: 三重循环, 最后对背包使用数量进行枚举
//
// 但是这里数据量大了会超时 -> 使用二进制优化
//
// 基本思路: 选了n个物品其实相当于选了 n个1个物品,
// 所以我们将{1..n}个物品都当成单独的一个可选物品 问题就转换成了二维了01背包问题
// 但是如果s个物品都拆成1 2 .. s个物品的话数据量其实是不变的n * m * s
//
// 假设能拆成1 2 3, 观察到, 三其实的没有必要的, 因为如果选了1
// 2两个就等价于选了一个3
//
// 参考二进制的表示, 任意数都可以表示成, 若干"2^n"的和, 如7 = "111" = 4 + 2 + 1,
// 3 = "11" = 2 + 1 所以只需差分成1 2 4 8等就能表示任意组合了
//
// 对于非2整次幂的数量我们可以拆成什么, 如101, 如果拆成1 2 4,
// 那么能够表示7就超出了数量限制6了 我们可以"抛弃最高位, 补足offset",  如10 = 7
// + 3 = 拆成 1 2 4,  3。1 2
// 4可以表示0~7的任意数在加上3的话最多最多就能表示到10了
//

// 且必须优化成一维
//
#define N 2010

struct Goods {
  int v, w;
};

int dp[N];

int main() {
  int n, m;
  vector<Goods> gd;
  gd.push_back({0, 0});
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    int v, w, s;
    cin >> v >> w >> s;
    for (int k = 1; k <= s; k *= 2) {
      s -= k;
      gd.push_back({k * v, k * w});
    }
    if (s > 0)
      gd.push_back({s * v, s * w});
  }

  n = gd.size() - 1;

  for (int i = 1; i <= n; i++) {
    for (int j = m; j >= gd[i].v; j--) {
        dp[j] = max(dp[j], dp[j - gd[i].v] + gd[i].w);
    }
  }
  cout << dp[m];
  return 0;
}

#include<iostream>
#include<vector>

using namespace std;

// 背包数量有限
//
// 算法: 三重循环, 最后对背包使用数量进行枚举

// 可以优化成一维
//
#define N 1010

int dp[N][N];

int v[N], w[N], s[N];

int main() {
  int n, m;
  cin >> n >> m;
  for(int i=1;i<=n;i++) cin >> v[i] >> w[i] >> s[i];

  for(int i=1;i<=n;i++) {
    for(int j=1;j<=m;j++) {
      dp[i][j] = dp[i-1][j];
      for(int k=1;k<=s[i] && k*v[i] <= j; k++) {
        dp[i][j] = max(dp[i][j], dp[i-1][j - k*v[i]] + k*w[i]);
      }
    }
  }
  cout << dp[n][m];
    return 0;
}

#include<iostream>
#include<vector>

using namespace std;

// 完全背包: 物品可以用无限次
//
// dp[i][j] 前i, j体积
//
//
// 状态表示
//  集合
//  属性
// 状态计算: 不重不漏 -> 每个方案选第i个的数量是确定的
//  集合划分: 选{0..k}个第i物品
//      prefix + k*v
//
//      所以转移f(i, j) = max(f(i-1, j - kv) + kw, ...)
//      (1) = max(f(i-1, j) + f(i-1, j-v) + w + < f(i-1, j-2v) + 2w > ...)
//      变量替换 j = j-v
//      f(i, j-v) = max(f(i-1, j - v - kv) + kw, ...)
//      (2) = max( f(i-1, j -v ) + < f(i-1, j-2v) + w > + f(i-1, j-3v) + 2w...)
//
//      可以看到(1)式[1..]部分与(2)式仅差w(max去一个)
//      所以转移方程
//      f(i, j) = max(f(i-1, j), f(i, j-v) + w)
//                                 ^
//                                 | 区别点
//              从小到大枚举时, 所需刚好在之前就生成了
//
//
// 优化分析
// 1. 只依赖前一项[i-1] -> 滚动更新，自己就是[i-1]
// 2. 刚好从小到大枚举, 前一步为后一步的需求([j-V[i]])做了铺垫

#define N 1010

int V[N], W[N];
int dp[N];

int main() {
  int n, m;
  cin >> n >> m;
  for(int i=1;i<=n;i++) cin >> V[i] >> W[i];

  // for(int i=1;i<=n;i++) {
    // for(int j=1;j<=m;j++) {
      // dp[i][j] = dp[i-1][j];
      // if(j >= V[i]) dp[i][j] = max(dp[i][j], dp[i][j-V[i]] + W[i]);
    // }
  // }
  for(int i=1;i<=n;i++) {
    for(int j=1;j<=m;j++) {
      dp[j] = dp[j];
      if(j >= V[i]) dp[j] = max(dp[j], dp[j-V[i]] + W[i]);
    }
  }

  cout << dp[m];

    return 0;
}

// 01背包, 每件物品只能0次或1次

#include<iostream>
#include<vector>

using namespace std;

// dp[i][j] 前i个, j重量, 价值最大

// 状态表示
//  集合: 前i件物品, 体积不超过j
//  属性: max
// 状态计算: 不重不漏
//  集合划分(状态转移): f[i][j] = 
//      不选第i个 dp[i][j] = dp[i-1][j]
//      选第i个 dp[i][j] = dp[i-1][j-w[i]] + v[i]
//
//
//
// 优化分析
//  1. 状态转移只依赖于i-1, 所以可以滚动更新，没覆盖时就是i-1
//  2. 因为状态转移还依赖j-v[i], 如果j从小到大那所依赖的j-v[i]历史就可能已经被覆盖

#define N 1010

int v[N], w[N];
int dp[N];

int main() {
  int n, wn;
  cin >> n >> wn;
  for(int i=1;i<=n;i++) {
    cin >> v[i] >> w[i];
  }
  for(int i=1;i<=n;i++) {
    for(int j=wn;j>=0;j--) {
      dp[j] = dp[j];
      if(j >= v[i]) {
        dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
      }
    }
  }
  cout << dp[wn];

    return 0;
}

#include<iostream>
#include<vector>
#include<climits>
#include<algorithm>

using namespace std;

// 算法: 重量和能力值相加, 从小到大排序, 所得求最大即答案
//
// 正确性证明:
// 1在最顶层
// 第i头牛的系数: w1 + w2 + ... + w{i-1} - si
// 第i+i头牛的系数: w1 + w2 + ... + wi - s{i+1}
//
// 两头牛交换顺序造成的影响
// 第i头牛的系数, 原i+1往上了: w1 + w2 + ... + w{i-1} + w{i+1} - s{i+1} , 所以 原 -si -> w{i+1} - s{i+1}
// 第i+1头牛的系数: w1 + w2 + ... + w{i-1} + w{i+1} - si, 原 wi - s{i+1} -> w{i+1} - si
//
// 第i头牛的系数, 原i+1往上了: w1 + w2 + ... + w{i-1} - s{i+1}
// 第i+1头牛的系数: w1 + w2 + ... + w{i-1} + w{i+1} - si
//
// 比较两组的最大值情况
// 原:               新: 
//  - si                - s{i+1}
//  wi - s{i+1}         w{i+1} - si
//  最大值比较等价于 wi - s{i+1}, w{i+1} - si比较
//  希望交换后最大值变小wi - s{i+1} >= w{i+1} - si  
//      -> wi + si >= w{i+1} + s{i+1}
//      所以当存在wi + si >= w{i+1} + s{i+1}时交换会让危险系数降低
//
//  所以重量和能力相加后从小到达排序后最大值会变小
#define N 100010

pair<int, int> cows[N];

int main() {
  int n;
  cin >> n;
  for(int i=0;i<n;i++) {
    int w, v;
    cin >> w >> v;
    cows[i] = {w+v, w};
  }
  sort(cows, cows+n);

  int sum = 0, res = INT_MIN;
  for(int i=0;i<n;i++) {
    int w = cows[i].second, v = cows[i].first - w;
    res = max(res, sum - v);
    sum += w;
  }
  cout << res;

    return 0;
}

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

using namespace std;

// 算法: 结论 -> 中位数
//
// 证明: 绝对值不等式
// |x - a| + |x - b| >= |a - b|
// 大白话: 两点之间任一一点距离最小, 否则(两点之外)至少都是x+一段
//
// 同理扩展到多个点 => 尽量取点在两点中间 => 否则多内层一段
//

#define N 100010

int ns[N];

int main() {
  int n;
  cin >> n;
  for(int i=0;i<n;i++) 
    cin >> ns[i];

  sort(ns, ns+n);

  int ans = 0;
  int m = ns[n/2];
  for(int i = 0;i<n;i++) {
    ans += abs(ns[i] - m);
  }

  cout << ans;




    return 0;
}