32939번 - 블록 쌓기

문제

$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)$

출력

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

제한

힌트