Cleaning

Interview

Time limit2sMemory limit1024 MB

Summary

For each window of K consecutive zones, visit them from highest to lowest priority and sum the moves between them. Output the minimum total.

Level: Medium6 of 10
Topics: Sliding window, Segment tree, Array
Solved: No attempts yet

Problem

Junseok works for a cleaning company. The area he cleans is a line of N zones numbered 1 through N in order. Zone i is adjacent to zones i-1 and i+1. Moving between two adjacent zones costs a distance of 1.

Each zone has a priority. The priority $A\_i$ of zone i is an integer from 1 to N, and a larger value means a higher priority. No two zones have the same priority.

Today Junseok wants to clean K of these zones first. The K zones he cleans must be consecutive. Within the chosen zones, he cleans them in order from highest priority to lowest.

Moving between distant zones takes a long time, so Junseok chooses K consecutive zones that minimize the total moving distance. Output the total moving distance for the best choice.

Input

The first line contains N and K, separated by a space. The second line contains the priorities $A\_1,A\_2,\cdots ,A\_N$ , separated by spaces.

Output

Print the minimum total moving distance over all possible choices of K consecutive zones.

Constraints

$1\leq K\leq N\leq 500\, 000$ , $1\leq A\_i\leq N$ , and if $i\neq j$ then $A\_i\neq A\_j$ .

Examples3

Example 1
Input
```
5 3
3 2 4 1 5
```
Expected output
```
3
```
Example 2
Input
```
8 4
4 3 2 5 8 1 6 7
```
Expected output
```
4
```
Example 3
Input
```
3 1
1 2 3
```
Expected output
```
0
```