주식의 신 timer 1s memory 512MB

미래를 예측하는 능력이 있는 정올이는 앞으로 N일간 정올 주식회사의 주가가 어떻게 변하는지 정확히 예측할 수 있다.

정올이는 예측한 결과를 바탕으로 정올 주식회사의 주식 한 주를 적당한 시점에 사고 적당한 시점에 팔아서 최대한의 이득을 얻으려고 한다.

정올 주식회사의 앞으로 N일간의 주가를 a_1, a_2, ..., a_N이라고 하자.

정올이가 i번째 날에 주식을 사고, j번째 날에 판다면 a_j - a_i만큼의 이득을 얻을 수 있다.

정올이는 자금이 넉넉하기 때문에 주가가 아무리 높아도 주식을 살 수 있고, 상황이 여의치 않을 경우 사자마자 바로 팔 수도 있다.

앞으로 N일간 정올 주식회사의 주가가 주어졌을 때,

정올이가 주식 한 주를 적당한 시점에 사고 적당한 시점에 팔아서 얻을 수 있는 최대 이득은 얼마일까?

단, 여러 번 사고 파는 행위는 막대한 수수료 손해가 있기에 딱 한 번 구매하고, 딱 한 번 판매하는 전략을 취한다.