결혼을 해야할 때가 되어서, 돈을 좀더 모으고자 주식에 관심을 가지게 된 광성(3x세 미혼)은 어떻게 하면 가장 주식을 성공적으로 거래할 수 있는지를 고민하고 있습니다.

하지만 회사업무와 고양이를 돌보느라 바쁜 광성은 하루에 최대 두번만 거래를 하기로 결정을 했습니다.

단, 기억력이 나빠서 두개의 거래를 동시에 진행은 안됩니다. 다시말하면, 한번 샀으면 또 살 수 없고 판 후에 구입해야 합니다. 

예를 들어 주가가 아래와 같이 변할 때,
  1000, 2000, 3000, 4000
1000, 2000 에서 각각 구입을 하고 3000, 4000에서 팔면 (1000원에 구입하여 3000원에 판매, 2000원에 구입해서 4000원에 판매) 4000을 이득으로 만들 수 있지만, 구입과 판매가 서로 겹쳐있으므로 이렇게 거래 할 수 없습니다. 거래가 겹치지 않기 위해서는 1000 에서 사고 2000에서 팔고, 3000에서 살고 4000에서 팔아야 하며, 이 때 총 이득은 2000이 됩니다.

시간순으로 주가가 주어졌을때, 최대 두번 사고 / 팔 때 얻을 수 있는 가장 큰 이득이 얼마인지를 알려주세요. (이득을 낼 수 없으면 거래를 하지 않거나, 한번만 거래해도 됩니다)

첫 줄에는 주어지는 주식 가격의 수 N (1 <= N <= 100,000)이 주어집니다.

두번째 줄부터 N+1 번째 줄 까지는 각 시간의 주가 P (1 <= P <= 1,000,000) 이 주어집니다.

얻을 수 있는 최대 이득이 얼마인지를 구해주세요.