Grandpa Quentin's Game#10219
Ryan and Jake are big fans of movies and board games. Since the cinemas are closed, they decide to have some fun with a game they found at Grandpa Quentin's. The game has the following rules:
The game board consists of cells arranged in a row, numbered from to .
Each cell contains an integer.
The player starts at cell number and must reach cell number , moving only forward.
Players cannot move outside the boundaries of the board.
The maximum step a player can take is . This means from cell number , a player can move to any cell between x + 1 and x + K, inclusive.
The player's score is the sum of the numbers in all the cells they step on during the game.
Ryan wants to maximize his score, while Jake aims to minimize his. They are curious about the difference in their scores when they use completely opposite strategies. Can you help them find this difference?
The first line contains two natural numbers, and .The second line contains integers a_1, a_2, \ldots, a_n, representing the numbers in each cell from the first to the last. 1 \le N, K \le 10^6, -10^9 \le a_i \le 10^9.
Output a single integer: the difference between Ryan's and Jake's scores.
Example 1
Example 2