Background

The best weapon is not always the most suitable one; only the most suitable weapon is the best. — Hall Magician W

Problem Description

Little M is facing the task of awakening their soul artifact, the magic ring.

There are $n$ nodes on the magic ring. Each node has a magic sprite, and each magic sprite has a fixed magic supply value. These magic supply values form a permutation of $0 \sim n-1$.

Little M may choose to activate or not activate a magic sprite. However, to awaken the magic ring, they must activate at least $k(\ge 2)$ magic sprites.

Each magic sprite produces an enchantment value regardless of whether it is activated:

• For an activated magic sprite, the enchantment value it produces is the square of its magic supply value.
• For a non-activated magic sprite, it looks left and right along the ring, respectively toward the nearest activated magic sprite on each side. It chooses the one with the larger magic supply value as the "target sprite", and the enchantment value it produces equals the product of the magic supply value of this "target sprite" and the distance that the line of sight passes through when looking at this "target sprite".

As a beginner, Little M wants, under the condition of activating the magic ring, to minimize the sum of the enchantment values of all magic sprites, so as to better control the energy of the magic ring.

Input Format

The first line contains two integers $n, k$.

The second line contains $n$ integers, representing the magic supply value of the magic sprite on each node.

Output Format

Output one integer in one line, representing the minimum possible sum of enchantment values.

5 2
3 0 1 4 2

7

10 3
2 0 1 5 8 3 4 9 6 7

53

Hint

[Sample 1 Explanation]

Activate the magic sprites with magic supply values $0$ and $1$.

• The magic sprite with magic supply value $3$ chooses the magic sprite with magic supply value $1$, producing an enchantment value of $1 \times 3 = 3$.
• The magic sprite with magic supply value $0$ is activated, producing an enchantment value of $0^2=0$.
• The magic sprite with magic supply value $1$ is activated, producing an enchantment value of $1^2=1$.
• The magic sprite with magic supply value $4$ chooses the magic sprite with magic supply value $1$, producing an enchantment value of $1 \times 1 = 1$.
• The magic sprite with magic supply value $2$ chooses the magic sprite with magic supply value $1$, producing an enchantment value of $1 \times 2 = 2$.

The total enchantment value produced is $7$.

[Constraints]

This problem uses bundled Subtask testdata.

For all testdata, $2\le k \le n \le 3000$, $k \le 100$. The magic supply values on each node form a permutation of $0\sim n-1$.

Translated by ChatGPT 5