히스토그램

밑변이 바닥에 평행한 직사각형 $N$개가 바닥에 연속으로 붙어 있는 히스토그램을 생각해 보자. 각 직사각형의 너비는 1로 같고, 왼쪽에서 $i$번째 직사각형의 높이는 정수 $H_i$이다.

아래 그림은 가능한 히스토그램의 한 예이다.

이 히스토그램 안에서 다음 조건을 모두 만족하는 직사각형을 $K$개 이하로 고른다. 밑변은 바닥과 평행하고, 임의의 두 직사각형은 내부가 겹치지 않으며(꼭짓점이나 모서리에서 맞닿는 것은 허용), 각 변의 길이는 정수이다. 고른 직사각형 넓이의 합이 최대가 되게 하려 하며, 이 최댓값을 $f(K)$라고 하자.

$f(1)$, $f(2)$, $f(3)$을 구하는 프로그램을 작성하라.

• $1 \le N \le 500\,000$
• $1 \le H_i \le 500\,000$ ($1 \le i \le N$)