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

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

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

입력 형식

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

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

출력 형식

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

예제 입력

3
1 2 3

예제 출력

4