图片被删除,或者路径改变
问题1473--Extract card

1473: Extract card

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 128 MiB

题目描述

题目背景:



  在肝了两个月之后,终于等到了胡桃开卡池的这一天…… “吆西!一万原石!必出!一定不要歪啊!”

  Y学长坐在电脑前祈祷着,然后移动鼠标点下了第一发十连。

  “开门红!出!..........没事。”

  第一发十连肯定是不会出货的,他哪有那么好的运气。

  “第二发!”

  “第三发!”

  此时,还剩下五千多原石.....

  “第四发,出!”

  依然没出,就这样,一直把原石抽光,一共七十抽了,依然没有出金。

  此时,Y学长脸上刚刚激动的表情已经暗淡下来,他捋了捋胸口的恶气,慢慢的疏散出去,拿出手机打开了充值界面。

  “唉,为了胡桃,为了奶香的一刀,氪了!大不了接下来一个月都吃馒头就辣条,648!”

  滴……充值成功。

  “第八十发,总该出了吧?”

  金光一闪,如愿出了金,他手心此刻已经溢出了紧张的汗,瞳孔聚精会神盯着屏幕,心里默念着:

  “不要歪,不要歪.....”

  鼠标一个个点下,最终,在最后一次点击的时候,一个熟悉的剪影倒映着在了他盯着电脑屏幕的瞳孔中,

  “啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊,怎么又是你!刻晴!”

  她气的直接从椅子上跳了起来,愤怒的锤着桌子……

  一边骂着,一边把刻晴升到了1命,

  “歪个琴也行啊,偏偏出了个命座,啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊,我的胡桃啊啊啊啊!”

  还有一发十连,虽说出金就是大保底,必出,但是怎么可能一发十连就直接出呢。

  果然,紫光一闪,没了。

  Y学长低着头,两个手紧紧的握住了拳头,用力的捶打了一下键盘,按键从键盘上飞出。他站起身来,拿起旅行剑走出了家门,向着刻晴家中走去......


题面描述:


  Y学长抽卡的紧张情绪令人扣动心弦,Liji学长嘴角微微一翘,决定为Y学长每次抽卡的结果都赋予一个整数w作为价值,这些价值有高有低。

       对于Y学长的抽卡,Liji学长提出了一种概念:

        如果存在wi1<w且wi+1<wi(需要保证wi1、w和wi+1一定是有意义的),那么就说Y学长的这次抽卡是激动的;如果存在wi1>w且wi+1>wi,那么就说Y学长的这次抽卡是失落的。
  Liji学长提出把Y学长抽卡的激动次数和失落次数的总和叫做崩溃程度,现在赋予你一个魔力:你可以改变最多一个抽卡的价值为任意值(必须在给出的数据范围内),Liji学长想知道在这种魔力的加持下,你能使Y学长的崩溃程度变成的最小值。

输入

输入第一行包含一个整数 t ( 1 ≤ t ≤ 1e3 ),代表 t 组测试数据。每组数据包括两行:第一行为一个整数 n ( 1≤ N ≤ 5e5 ),紧接着第二行为 n 个整数 w_{i}i ( 0 ≤ w_{i}i ≤ 1e8 ),代表Y学长每次抽卡结果的价值,每两个整数中间用空格隔开。数据保证 t 组数据 n 的总和 ≤ 5e5

输出

对应每个输入包含一个输出,每个输出占一行,为你能使Y学长的崩溃程度变成的最小值(改变的位置不一定是唯一的,故只需要输出最小崩溃程度即可)

样例输入 Copy

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

样例输出 Copy

0
0
1
0

提示

样例解释:(索引均从1开始)
在第一个测试案例中,将 w2 改为 2 的结果是没有激动和失落。 

在第二个测试案例中,最佳答案是不施展魔力。 

在第三个测试案例中,将 w3 改为 6 的结果是只有一次失落(位于索引5处)。 

在第四个测试案例中,将 w3 改为 6 的结果是没有激动和失落。 

请避免使用全局变量!

来源/分类