Penchick and Modern Monument

A. Penchick and Modern Monument

Problem

Amidst skyscrapers in the bustling metropolis of Metro Manila, the newest Noiph mall in the Philippines has just been completed! The construction manager, Penchick, ordered a state-of-the-art monument to be built with $n$ pillars.

The heights of the monument’s pillars can be represented as an array $h$ of $n$ positive integers, where $h_i$ represents the height of the $i$-th pillar for all $i$ between $1$ and $n$.

Penchick wants the heights of the pillars to be in non-decreasing order, i.e. $h_i\le h_{i+1}$ for all $i$ between $1$ and $n-1$. However, due to confusion, the monument was built such that the heights of the pillars are in non-increasing order instead, i.e. $h_i\ge h_{i+1}$ for all $i$ between $1$ and $n-1$.

Luckily, Penchick can modify the monument and do the following operation on the pillars as many times as necessary:

• Modify the height of a pillar to any positive integer. Formally, choose an index $1\le i\le n$ and a positive integer $x$. Then, assign $h_i:=x$.

Help Penchick determine the minimum number of operations needed to make the heights of the monument’s pillars non-decreasing.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le 1000$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1\le n\le 50$) — the number of pillars.

The second line of each test case contains $n$ integers $h_1,h_2,\dots ,h_n$ ($1\le h_i\le n$ and $h_i\ge h_{i+1}$) — the height of the pillars.

Please take note that the given array $h$ is non-increasing.

Note that there are no constraints on the sum of $n$ over all test cases.

Output

For each test case, output a single integer representing the minimum number of operations needed to make the heights of the pillars non-decreasing.

Example

Input

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

Output

4
1
0

Note

In the first test case, the initial heights of pillars are $h=[5,4,3,2,1]$.

• In the first operation, Penchick changes the height of pillar $1$ to $h_1:=2$.
• In the second operation, he changes the height of pillar $2$ to $h_2:=2$.
• In the third operation, he changes the height of pillar $4$ to $h_4:=4$.
• In the fourth operation, he changes the height of pillar $5$ to $h_5:=4$.

After the operation, the heights of the pillars are $h=[2,2,3,4,4]$, which is non-decreasing. It can be proven that it is not possible for Penchick to make the heights of the pillars non-decreasing in fewer than $4$ operations.

In the second test case, Penchick can make the heights of the pillars non-decreasing by modifying the height of pillar $3$ to $h_3:=2$.

In the third test case, the heights of pillars are already non-decreasing, so no operations are required.

Code

// #include <iostream>
// #include <algorithm>
// #include <cstring>
// #include <stack>//栈
// #include <deque>//堆/优先队列
// #include <queue>//队列
// #include <map>//映射
// #include <unordered_map>//哈希表
// #include <vector>//容器，存数组的数，表数组的长度
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
typedef long long ll;
const ll N=1e2+10;
ll a[N],f[N];

void solve()
{
    ll n;
    cin>>n;

    for(ll i=1;i<=n;i++) cin>>a[i];

    for(ll i=1;i<=n;i++)
    {
        f[i]=1;
        for(ll j=1;j<i;j++)
        {
            if(a[j]<=a[i]) f[i]=max(f[i],f[j]+1);
        }
    }

    ll res=0;
    for(ll i=1;i<=n;i++) res=max(res,f[i]);

    cout<<n-res<<endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    ll t;
    cin>>t;
    while(t--) solve();
    
    return 0;
}