Reversort

Design a hardware module for the Reversort problem.

You are given a list of distinct integers. Repeatedly apply this procedure:

1. At position i, find the minimum element in the suffix from i to the end.
2. Reverse the subarray from i through that minimum element.
3. Add the length of that reversed subarray to the total cost.

Continue until the list is sorted.

Your task is to output the total Reversort cost.

Hardware I/O Encoding

• l is a one-dimensional input stream of unsigned 8-bit integers, presented left to right
• the stream contains up to 50 elements
• the input values are distinct
• the output is a single 16-bit unsigned integer equal to the total Reversort cost

Examples

Example 1

• logical list: [1, 2]
• encoded l: [1, 2]
• output: 1

The list is already sorted. Reversort still performs one length-1 reversal, so the total cost is 1.

Example 2

• logical list: [4, 2, 1, 3]
• encoded l: [4, 2, 1, 3]
• output: 6

One valid trace is:

1. reverse [4, 2, 1] -> [1, 2, 4, 3], cost 3
2. reverse [2], cost 1
3. reverse [4, 3] -> [3, 4], cost 2

Total cost: 3 + 1 + 2 = 6.

Example 3

• logical list: [3, 1, 2]
• encoded l: [3, 1, 2]
• output: 4

Source: Google Code Jam 2021 Qualification Round - Reversort