시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB3861269641.379%

문제

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

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

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

입력

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

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

출력

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

예제 입력 1

3
1 2 3

예제 출력 1

4

농부가 $A_1$, $A_2$, $A_3$을 따서 꽃다발을 만들면 꽃다발의 아름다움은 $(1-2)^2+(2-3)^2=2$다.

농부가 $A_1$, $A_3$을 따서 꽃다발을 만들면 꽃다발의 아름다움은 $(1-3)^2=4$다.

꽃을 하나만 따는 경우는 인접한 꽃이 없으므로 고려하지 않는다.