Cheerio Contest 1 S4 - Mystery Boxes

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Java 2.0s
Python 2.0s
Memory limit: 512M

Problem type

There is a line of N boxes on a table, indexed from 1 to N. Each box is assigned a number a_i between 1 and M such that every number from 1 to M appears at least once. In order to open a box with a_i = m, you must have already opened a box with a_i = m-1. You do not need to open anything before opening a box with a_i = 1.

In addition, to get from index i to index j, you need to travel a distance of |j-i|. You are initially at index 0, and all the boxes are closed. What is the minimum distance you need to travel in order to open a box with a_i = M?


For all subtasks:

  • 1 \le a_i \le M \le N
  • There is always at least one box with a_i = m for all 1 \le m \le M.
Points Awarded N
5 points 1 \le N \le 4\,000
10 points 1 \le N \le 5 \times 10^5

Input Specification

The first line contains two integers N and M.

The second line contains N integers a_i.

Output Specification

Output the minimum distance required. Please note that this number may not fit inside a 32-bit integer.

Sample Input

4 3
3 1 2 2

Sample Output


Explanation for Sample Output

Starting from index 0, we go to index 2, then to index 3 and then back to index 1. The total distance travelled is |2-0| + |3-2| + |1-3| = 5. It can be proven that this is the minimal distance required.


There are no comments at the moment.