25759번 - 들판 건너가기

문제

농부는 $N$개의 꽃이 일렬로 활짝 핀 들판을 왼쪽에서 오른쪽으로 걷고 있다. 심심한 농부는 들판에 핀 꽃을 몇 개 따서 꽃다발을 만들려 한다.

꽃다발의 아름다움은 꽃을 딴 순서대로 놓았을 때 (인접한 꽃의 아름다움 차이)$^2$의 전체 합으로 정의된다.

산수를 어려워하는 농부는 가장 아름다운 꽃다발을 만들 수 있는 방법을 물어봤다. 농부가 만들 수 있는 꽃다발의 가장 높은 아름다움 값을 구해주자.

입력

첫 번째 줄에 들판에 핀 꽃의 개수 $N$이 주어진다. (2ドル \le N \le 100,000円$)

두 번째 줄에 $i$번째 꽃의 아름다움 값 $A_i$이 공백으로 구분되어 주어진다. (1ドル \le A_i \le 100$)

출력

꽃다발의 가장 높은 아름다움 값을 출력한다.

제한

힌트