D. Sorting By Multiplication

Problem - D - Codeforces

思路：我们首先考虑当只能乘以正数时，那么变为单调增的方法就是找所有w[i]>=w[i+1]的对数，因为如果存在一个w[i]>=w[i+1]，那么我们一定至少需要进行一次操作，并且我们还知道我们进行一次操作最多只会破坏一对w[i]>=w[i+1]（假如我们能够破坏两对，w[l]>=w[l+1]，w[r]>=w[r+1]，因为我们要破坏第一对，那么我们只能够对w[l+1]乘，并且我们又要破坏第二对，那么我们需要对w[r+1]乘，但是我们发现我们对w[r+1]乘的同时一定会对w[r]乘，所以我们一定不会破坏第二对，所以我们知道最多只会破坏一对），那么接下来我们只需要计算一下有多少对w[i]>=w[i+1]即可，如果加上了能够乘以负数，代表我们可以将一段递减的序列通过乘以一次负数得到递增的序列，那么我们就会想到一种方法，将前面的一部分得到递减的，后面一部分得到递增的，那么只需要这两部分的次数和+1，就能够得到递增的，那么我们会想到一个问题，一个是为什么前面递减的一定是连续的呢，比如说先递增再递减，那么我们能够发现如果我们将递减的乘以负数之后，前面递增的只能每次操作一次将其变为负数，然后拼接起来才是递增的，但是其实我们是可以先通过一次一个的将递增的变为递减的，将两个递减的拼接到一起，然后再对整体操作一次，变为递增的，那么答案并不会变差，所以一定可以前缀递减的，所以我们可以枚举那个点作为增减的分段点，然后求一个min(l[i]+1+r[i+1])即可，同时还要注意对r[1]去一个min，因为可能整体就是递增的

// Problem: D. Sorting By Multiplication
// Contest: Codeforces - Educational Codeforces Round 154 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1861/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
 
#include
#include
#include
#define fi first
#define se second
#define i128 __int128
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> PII;
const double eps=1e-7;
const int N=5e5+7 ,M=5e5+7, INF=0x3f3f3f3f,mod=1e9+7,mod1=998244353;
const long long int llINF=0x3f3f3f3f3f3f3f3f;
inline ll read() {ll x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') {x=(ll)x*10+c-'0';c=getchar();} return x*f;}
inline void write(ll x) {if(x < 0) {putchar('-'); x = -x;}if(x >= 10) write(x / 10);putchar(x % 10 + '0');}
inline void write(ll x,char ch) {write(x);putchar(ch);}
void stin() {freopen("in_put.txt","r",stdin);freopen("my_out_put.txt","w",stdout);}
bool cmp0(int a,int b) {return a>b;}
template<typename T> T gcd(T a,T b) {return b==0?a:gcd(b,a%b);}
template<typename T> T lcm(T a,T b) {return a*b/gcd(a,b);}
void hack() {printf("\n----------------------------------\n");}
 
int T,hackT;
int n,m,k;
int w[N];
int l[N],r[N];
 
void solve() {
	n=read();
	
	for(int i=1;i<=n;i++) w[i]=read(),l[i]=r[i]=0;
	r[n+1]=0;
	
	for(int i=2;i<=n;i++) {
		l[i]=l[i-1];
		if(w[i-1]<=w[i]) l[i]++;
	}
	for(int i=n-1;i>=1;i--) {
		r[i]=r[i+1];
		if(w[i]>=w[i+1]) r[i]++;
	}
	
	int ans=r[1];
	for(int i=1;i<=n;i++) ans=min(ans,l[i]+1+r[i+1]);
	
	printf("%d\n",ans);
}   
 
int main() {
    // init();
    // stin();
	// ios::sync_with_stdio(false); 
 
    scanf("%d",&T);
    // T=1; 
    while(T--) hackT++,solve();
    
    return 0;       
}