비트코인 투자

비트코인은 사토시 나카모토라는 이름으로 공개된 디지털 자산이자 결제 시스템이다. 이 이름이 실명인지 가명인지, 한 사람인지 여러 사람인지는 알려지지 않았다.

비트코인 한 개의 유로 가격은 빠르게 변한다. 어느 날에는 800유로였다가 이틀 뒤에 20유로로 떨어지기도 한다.

앞으로의 비트코인 대 유로 환율을 모두 안다고 하자. 최대한 큰 이익을 내고 싶다. 처음에는 비트코인이 없다. 어느 날에 비트코인을 정확히 한 개 사고, 같은 날이나 그 뒤의 어느 날에 판다. 판 가격에서 산 가격을 뺀 값이 이익이다.

예를 들어 앞으로 10일 동안 비트코인 한 개의 가격이 다음과 같다고 하자.

1일에 5유로로 사서 2일에 11유로로 팔면 이익은 6유로다. 4일에 2유로로 사서 6일에 10유로로 팔면 이익은 8유로이고, 이 가격으로 낼 수 있는 가장 큰 이익은 8유로다.

환율 목록이 주어지면 낼 수 있는 가장 큰 이익을 구하라. 사는 것도 파는 것도 한 번뿐이고, 파는 날은 사는 날보다 앞설 수 없다. 같은 날에 사고팔면 이익이 0이므로 답은 음수가 되지 않는다.

첫째 줄에 환율의 개수 $n$이 주어진다 ($1 \le n \le 100000$).

둘째 줄에 $n$일 동안 비트코인 한 개의 유로 가격이 정수 $n$개로 주어진다. 각 가격은 1 이상 10000 이하다.

낼 수 있는 가장 큰 이익을 출력한다.