Make It Good CodeForces - 1385C rat1200

You are given an array a consisting of n integers. You have to find the length of the smallest (shortest) prefix of elements you need to erase from a to make it a good array. Recall that the prefix of the array a=[a1,a2,…,an] is a subarray consisting several first elements: the prefix of the array a of length k is the array [a1,a2,…,ak] (0≤k≤n).

The array b of length m is called good, if you can obtain a non-decreasing array c (c1≤c2≤⋯≤cm) from it, repeating the following operation m times (initially, c is empty):

select either the first or the last element of b, remove it from b, and append it to the end of the array c.

For example, if we do 4 operations: take b1, then bm, then bm−1 and at last b2, then b becomes [b3,b4,…,bm−3] and c=[b1,bm,bm−1,b2].

Consider the following example: b=[1,2,3,4,4,2,1]. This array is good because we can obtain non-decreasing array c from it by the following sequence of operations:

take the first element of b, so b=[2,3,4,4,2,1], c=[1];

take the last element of b, so b=[2,3,4,4,2], c=[1,1];

take the last element of b, so b=[2,3,4,4], c=[1,1,2];

take the first element of b, so b=[3,4,4], c=[1,1,2,2];

take the first element of b, so b=[4,4], c=[1,1,2,2,3];

take the last element of b, so b=[4], c=[1,1,2,2,3,4];

take the only element of b, so b=[], c=[1,1,2,2,3,4,4] — c is non-decreasing.

Note that the array consisting of one element is good.

Print the length of the shortest prefix of a to delete (erase), to make a to be a good array. Note that the required length can be 0.

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1≤t≤2⋅104) — the number of test cases. Then t test cases follow.

The first line of the test case contains one integer n (1≤n≤2⋅105) — the length of a. The second line of the test case contains n integers a1,a2,…,an (1≤ai≤2⋅105), where ai is the i-th element of a.

It is guaranteed that the sum of n does not exceed 2⋅105 (∑n≤2⋅105).

Output

For each test case, print the answer: the length of the shortest prefix of elements you need to erase from a to make it a good array.

Example

Input

5

4

1 2 3 4

7

4 3 3 8 4 5 2

3

1 1 1

7

1 3 1 4 5 3 2

5

5 4 3 2 3

Output

4

2

3

逆序找最大值

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<cstdio>
#include<vector>
#include<set>
#include<cstring>
#include<cstdlib>
#include<time.h>
#include<stack>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=100;
typedef long long ll;
ll mod=1e8+7;
ll num,f[maxn];
struct mat{
    ll m[maxn][maxn];
}ans,a;//結果矩陣 輸入矩陣
ll mode(ll a,ll b){
    ll sum=1;
    a=a%mod;
    while(b){
        if(b&1)
            sum=(sum*a)%mod;
        b/=2;
        a=(a*a)%mod;
    }
    return sum;
}//快速幂
ll inv(ll a,ll b){
    return(a*mode(b,mod-2))%mod;
}//逆元
ll gcd(ll a, ll b) {
	return b?gcd(b, a%b):a;
}//a,b最大公因數
ll lcm(ll x, ll y){
     return x / gcd(x, y)*y; 
}//最小公倍數
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1;y=0;
        return a;
    }
    int r=exgcd(b,a%b,x,y);
    int temp=y;
    y=x-(a/b)*y;
    x=temp;
    return r;
}// 拓展歐幾裡得 ax+by=d的一組解
mat mul(mat a,mat b,int n){
    mat c;
    memset(c.m,0,sizeof(c.m));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                c.m[i][j]=(c.m[i][j]+(a.m[i][k]*b.m[k][j])%mod)%mod;
    return c;
}//矩陣a*b 大小為n
mat _power(mat a,int b,int n){
    memset(ans.m,0,sizeof(ans.m));
    for(int i=1;i<=n;i++)
        ans.m[i][i]=1;
    while(b){
        if(b&1)
            ans=mul(a,ans,n);
        a=mul(a,a,n);
        b>>=1;
    }
    return ans;
}//矩陣a^b
 int vis[maxn];
void init(int n){
    for(int i=2;i<=n;i++){
        if(vis[i])continue;
        for(int j=i*2;j<=n;j+=i)vis[j]=1;
    }
}//埃篩素數
//for(int i=2;i<=n;i++)
//if(!vis) cout<<i<<endl;
int oula(int x)//歐拉函數
{
	int i,j;
	int num = x;
	for(i = 2; i*i <= x; i++)
	{
		if(x % i == 0)
		{
			num = (num/i)*(i-1);
			while(x % i == 0)
			{
				x = x / i;
			}
		}
	}
	if(x != 1) num = (num/x)*(x-1);
	return num;
}//歐拉函數 小于n且與n互質的正整數個數
const int mx=1e6+5;
int b[mx];
int main()
{
   int t;
   cin>>t;
   while(t--){
       int n;
       b[0]=-INF;
       cin>>n;
       for(int i=1;i<=n;i++)
            cin>>b[i];
        int cnt=0,flag=0;
        for(int i=n;i>=1;i--)
            if(b[i-1]<b[i]) cnt=1;
        else if(cnt==1&&b[i-1]>b[i]){
            cout<<i-1<<endl;
            flag=1;break;
        }
        if(flag==0)cout<<0<<endl;
   }
  system("pause");
  return 0;
}