블록 쌓기

시간 제한1초메모리 제한1024 MB

요약

N개 칸의 목표 블록 수 a_i가 주어질 때, 구간 쌓기 연산의 최소 횟수와 그 횟수에서 구간 길이 제곱합의 최소 비용을 구합니다.

문제

$N$ 개의 칸이 일렬로 나열되어 있고, 이 위에 블록을 쌓으려고 한다. 처음에는 어느 칸에도 블록이 없다. 한 번의 시행으로 다음과 같이 블록을 쌓을 수 있다.

$1 \leq l \leq r \leq N$ 을 만족하는 두 정수 $l$ , $r$ 을 고른다. $l \leq i \leq r$ 인 모든 $i$ 에 대해 $i$ 번째 칸에 블록을 한 개씩 쌓는다. 이때 $(r-l+1)^2$ 만큼의 비용이 든다.

목표는 $1 \leq i \leq N$ 인 모든 $i$ 에 대해 $i$ 번째 칸의 블록 개수가 정확히 $a_i$ 개가 되도록 하는 것이다. 필요한 시행의 최소 횟수와, 시행 횟수를 최소로 할 때의 비용 최솟값을 구하라.

첫 번째 줄에 칸의 개수 $N$ 이 주어진다. $(1 \leq N \leq 300\ 000)$

두 번째 줄에 $a_1, a_2, \cdots, a_N$ 이 공백으로 구분되어 주어진다. $(0 \leq a_i \leq 1\ 000\ 000)$

시행의 최소 횟수와, 시행 횟수를 최소로 할 때의 비용 최솟값을 공백으로 구분하여 출력한다.