공상에 잠긴 주식 중개인

주식 중개인 지나 리드는 오늘따라 일이 한가하다. 솔리테어를 몇 판 돌리는 사이에 지나는 공상에 잠긴다. 미래를 알아맞히는 일은 어렵다. 하지만 과거로 돌아가서 주가 기록을 그대로 알고 있다면 이익을 최대로 불릴 수 있지 않을까?

지나는 이런 상상을 한다. 며칠 전으로 돌아가면서 겨우 $100만 들고 간다면, 세상에서 가장 변동이 심한 주식인 Rollercoaster Inc.를 알맞은 시점에 사고팔아서 얼마나 벌 수 있을까? 테네리페의 저택에서 편하게 은퇴할 만큼 벌 수 있을까?

지나는 주식을 쪼개서 살 수 없고 정수 주 단위로만 산다. Rollercoaster Inc.의 총 주식 수는 100000주이므로 지나는 어느 순간에도 100000주를 넘게 가질 수 없다. 지나의 공상 속 세계는 단순하다. 주식을 사고팔 때 수수료가 없고, 주가는 하루에 한 번만 바뀌며, 지나의 거래는 주가에 영향을 주지 않는다.

첫째 줄에 지나가 공상 속에서 거슬러 올라가는 날짜 수 $d$ ($1 \le d \le 365$)가 주어진다. 다음 $d$개 줄 중 $i$번째 줄에는 $i$일째에 지나가 Rollercoaster Inc. 주식 한 주를 사거나 팔 수 있는 가격 $p_i$ ($1 \le p_i \le 500$)가 주어진다. 날짜는 오래된 순서대로 주어진다.

마지막 날의 거래까지 마쳤을 때 지나가 가질 수 있는 돈의 최댓값을 출력한다. 가지고 있는 주식은 돈으로 세지 않으므로 마지막 날에는 주식을 모두 팔아 현금으로 바꾼다. 답은 $2^{32}$보다 클 수 있다.