Jordan has recently received a game that contains many cubic-shaped blocks. By stacking them, he can build towers of great height, and by placing the towers next to each other, he can create what he calls castles. However, he only likes castles that satisfy the condition that the number of blocks in a tower is always less than or equal to that of the tower immediately to its left. Additionally, he likes to describe these castles with a sequence of integers $$$(a_i)$$$ such that each $$$a_i$$$ corresponds to the number of blocks in the $$$i$$$-th tower. After playing with this type of castle, he has realized that he can also describe them with a sequence $$$(b_i)$$$ such that each $$$b_i$$$ corresponds to the number of blocks on the $$$i$$$-th floor of the castles. Thus, for the castle:

XX

XX

the sequence $$$(a_i)$$$ would be $$$a_1 = 3, a_2 = 2$$$ and the sequence $$$(b_i)$$$ would be $$$b_1 = 2, b_2 = 2, b_3 = 1$$$.

Jordan says that a castle is pretty if the two sequences match, as happens with the castle:

XXX

Given a castle described by the sequence $$$(a_i)$$$, determine the minimum number of blocks that need to be removed to convert it into a pretty castle.

$$$t \leq 40$$$, $$$n \leq 100000$$$, $$$a_i \geq a_{i+1}$$$ and $$$a_i \leq 10^9$$$.

12 points: $$$n \leq 8$$$, $$$a_i \leq 8$$$.

19 points: $$$n \leq 1000$$$, $$$a_i \leq 1000$$$.

31 points: $$$a_i \leq 100000$$$.

38 points: No additional restrictions.