Title: Give you n numbers, ask you to sort these n numbers, there is a sort operation, select a number, move to the right until you encounter the number greater than the number that is greater than the number.

Ask a few times to operate a few times

problem -solving ideas: Sweep from right to left, only the highest bit to the position can the lowest position, otherwise it will be stuck in the middle

Use POS to show that the position is scanned.

Discuss

1. If Val [POS] <max, it means that the position should be MAX, but the number is smaller than MAX, which moves all the number of [VAL [POS] + 1, MAX] to move all the number Then update max = value

2. If value [pos]> max, this is not to worry, because we are already calculated before, so I skip it directly

3. If value [pos] == max, it means that Max –

```
#include <cstdio>
#include <cstring>
const int N = 1000010;
int val[N];
int n, cas = 1;
void init() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &val[i]);
}
void solve() {
int pos = n, Max = n, ans = 0;
while (pos) {
if (val[pos] < Max ) {
ans += Max - val[pos];
Max = val[pos] - 1;
}
if (val[pos] == Max) Max--;
pos--;
}
printf("Case #%d: %d\n", cas++, ans);
}
int main() {
int test;
scanf("%d", &test);
while (test--) {
init();
solve();
}
return 0;
}
```