27236번 - 신도시 개발

BOJ 도시에는 $1$번부터 $N$번까지 번호가 붙은 $N$개의 토지가 일렬로 있고, 이 중 이미 분양된 토지가 $M$개 있다.

BOJ 도시의 시장인 청한이는 BOJ 도시를 개발하기 위해 아직 분양되지 않은 토지 중 $K$개를 분양하려고 한다. 단 도시와 멀면 토지의 수요가 줄어들기 때문에, 중심으로부터 멀어질수록 할인하여 분양하려고 한다. 구체적으로, 어떤 토지를 분양하는 시점에 이 토지의 왼쪽과 오른쪽에 있는 분양된 토지의 개수 차이를 $D$라고 할 때, 이 토지는 원래 가격에서 $D$만큼 할인하여 분양한다.

청한이는 BOJ 도시의 토지 중 $K$개를 골라 적절한 순서로 분양해서 최대한의 이익을 내고 싶다. 즉, 분양한 토지들이 할인된 양의 총합을 최소화해야 한다. 토지는 청한이가 정한 순서대로 하나씩 분양하며, 동시에 여러 개의 토지를 분양할 수 없다. 최적의 방법으로 토지를 분양했을 때, 할인된 양의 총합은 얼마인지 구하시오.

첫 번째 줄에 BOJ 도시의 토지의 개수 $N$, 이미 분양된 토지의 개수 $M$, 앞으로 분양할 토지의 개수 $K$가 주어진다.

두 번째 줄에 이미 분양된 토지의 번호를 나타내는 $M$개의 정수 $x_i$가 공백으로 구분되어 주어진다.

최적의 방법으로 토지를 분양했을 때, 분양한 토지들의 할인된 양의 총합을 출력한다.

• $1\leq N\leq 300\,000$
• $1\leq M, K \leq N$
• $M + K\leq N$
• $1\leq x_i\leq N$
• 주어지는 모든 $x_i$는 서로 다르다.