Minimum Additions to Achieve a Strictly Increasing Skyline

Given the heights of buildings in a skyline, your task is to determine the minimum number of additional buildings required so that the skyline becomes strictly increasing from left to right.

The original sequence of building heights is provided as an array. For each building from the second element onward, if its height is not strictly greater than the maximum height seen so far, then one additional building must be added. Formally, for a sequence \(a_1, a_2, \dots, a_n\), you need to count how many indices \(i \ (2 \leq i \leq n)\) satisfy \[ a_i \leq \max\{a_1, a_2, \dots, a_{i-1}\}. \]

For example, given the array [1, 2, 2, 3, 4], you need to add one building because the third building (with height 2) is not strictly greater than the previous maximum (2).

inputFormat

The first line contains a single integer \(T\) representing the number of test cases. Each test case consists of two lines:

• The first line contains an integer \(N\), the number of buildings.
• The second line contains \(N\) space-separated integers representing the heights of the buildings.

outputFormat

For each test case, print a single line containing the minimum number of additional buildings required to make the skyline strictly increasing.

## sample

3
5
1 2 2 3 4
4
4 3 2 1
6
1 3 3 5 4 6

1
3
2

</p>