You are given k bags and a 0-indexed integer array, weights, where weights[i] represents the weight of the $i^{th}$ marble.

Your task is to divide the marbles into the k bags according to the following rules:

1. No bag can be empty.

2. If the $i^{th}$ marble and the $j^{th}$ marble are placed in the same bag, then all marbles with indexes between i and j (inclusive) must also be placed in that same bag.

3. If a bag contains all the marbles from index i to j (inclusive), its cost is calculated as weights[i] + weights[j].

After distributing the marbles, the sum of the costs of all the k bags is called the score.

Return the difference between the maximum and minimum scores achievable by distributing the marbles into the k bags.

Constraints:

• $1 \leq$ k $\leq$ weights.length $\leq 10^5$

• $1 \leq$ weights[i] $\leq 10^9$

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding on how to solve this problem.

Implement your solution in the following coding playground.