n = gets.to_i
as = gets.split.map &:to_i
cnt = 10001
dp = [1000] + [-1000000000] * (cnt-1)
prev = 10000
as.each do |a|
  next if prev == a
  dp1 = nil
  if prev > a # buy
    dp1 = [dp[0]]
    (1...cnt).map do |s|
      max = dp[s]
      m = dp1[s-1]-a
      max = [max, m].max if m >= 0
      dp1[s] = max
    end
  else # sell
    dp1 = []
    dp1[cnt-1] = dp[cnt-1]
    (cnt-2).downto(0).map do |s|
      max = dp[s]
      max = [max, dp1[s+1]+a].max
      dp1[s] = max
    end
  end
  prev = a
  dp = dp1
  #p dp
end
p dp[0]