Grouping Increases

您将得到一个大小为 n 的数组 a。您将执行以下过程来计算惩罚：将数组 a 拆分为两个子序列 s 和 t（可能为空），使 a 的每个元素都在 s 或 t 中。
对于大小为 m 的数组 b，将数组 b 的惩罚 ?p(b) 定义为介于 1 和 m?1 之间的索引 i 的数量，其中 bi＜ bi+1。
您将收到的总罚款为 p(s)+p(t).
如果您以最佳方式执行上述过程，请找出您将收到的可能的最低处罚。
注意，将数组 a=[3,1,4,1,5] 拆分为 (s,t)的一些有效方法是 ([3,4,1,5],[1])、([1,1],[3,4,5])和([],[3,1,4,1,5])，而将数组a拆分为([3,4,5],[1]）、([3,1,4,1],[1,5])、([1,3,4,1],[1,5])和([1,3,4],[5,1])的一些无效方法。

输入
每个测试包含多个测试用例。第一行包含一个整数t（1 ≤ t ≤ 1e4）——测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 n（1 ≤ n ≤ 2e5）——数组a的大小。
第二行包含n个整数 a1，a2，…，an（1 ≤ ai ≤ n）——数组a的元素。
保证所有测试用例的 n 之和不超过 2e5。

输出
对于每个测试用例，输出一个整数，表示您将收到的可能的最小惩罚。

Input
5
5
1 2 3 4 5
8
8 2 3 1 1 7 4 3
5
3 3 3 3 3
1
1
2
2 1

Output
3
1
0
0
0

注：
在第一个测试用例中，拆分a的一种可能方法是 s=[2,4,5] 和 t=[1,3]。惩罚为 p(s)+p(t)=2+1=3。
在第二个测试用例中，拆分a的一种可能方法是 s=[8,3,1] 和 t=[2,1,7,4,3]。惩罚为 p(s)+p(t)=0+1=1。
在第三个测试用例中，拆分a的一种可能方式是 s=[] 和 t=[3,3,3,3,3]。惩罚为 p(s)+p(t)=0+0=0。

解析：

我们建立两个空数组 b和 c，之后将 a数组中的元素一个接一个插入 b和c，使得?a 中相邻 ai<ai+1 的个数减少。
惩罚函数只取决于相邻元素，所有我们只关心 b和 c的最后一个元素的值。假设我们已经将 a1，a2，…，ai?1 插入到数组 b和 c中，现在我们想要插入ai，假设 x 和 y 分别是数组 b和 c的最后一个元素。

假设 x ≤ y,
如果ai ≤ x，则将ai插入到具有较小最后一个元素的数组的后面。
如果y＜ai，则将ai插入到具有较小最后一个元素的数组的后面。
如果x＜ai ≤y，则将ai插入到最后一个元素较大的数组的后面。
当数组 b和c 为空时，令 x和y 无穷大。

ai ≤ x 在这种情况下，ai 不大于两个数组的最后一个元素，因此将 ai 插入任一数组的后面不会增加额外的惩罚。然而，最好将 ai 插入到最后一个元素较小的数组中，这样将来我们就可以在没有额外惩罚的情况下将更大范围的值插入到新数组中。
y＜ai 在这种情况下，ai 大于两个数组的最后一个元素，因此将 ai 插入任一数组的后面将导致1个额外的惩罚。然而，最好将 ai 插入到最后一个元素较小的数组中，这样将来我们就可以在没有额外惩罚的情况下将更大范围的值插入到新数组中。
x< ai ≤y 在这种情况下，如果我们将ai插入到最后一个元素较大的数组的后面，则不会有任何额外的惩罚。然而，如果我们将 ai 插入到最后一个元素较小的数组的后面，则会有 1 的额外惩罚。前者总是比后者好。这是因为，如果我们考虑在两种情况下对其余元素 ai+1 到 an 做出相同的选择，则最多会有一次，前一种情况会比后一种情况多增加一个惩罚，因为前一种场景在插入 ai 后的最后一个元素较小。在这之后，两种情况下的阵列背面将变得相同，因此，前一种情况永远不会不那么优化。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const int N=2e6+10;
int t,n;
int a[N];
int s[N],p[N];
signed main()
{
    ios;
    cin>>t;
    while (t--)
    {
        cin>>n;
        for (int i=1;i<=n;i++) cin>>a[i];
        int l=0,r=0;
        s[l]=2e9,p[r]=2e9;
        for (int i=1;i<=n;i++)
        {
            int x=a[i];
            if (s[l]<p[r])
            {
                if (s[l]>=x||p[r]<x) s[++l]=x;
                else p[++r]=x;
            }
            else 
            {
                if (p[r]>=x||s[l]<x) p[++r]=x;
                else s[++l]=x;
            }
        }
        int cnt=0;
        for (int i=1;i<l;i++)
        {
            if (s[i]<s[i+1]) cnt++;
        }
        for (int i=1;i<r;i++)
        {
            if (p[i]<p[i+1]) cnt++;
        }
        cout<<cnt<<endl;
    }
    return 0;
}


//精简版 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const int N=2e6+10;
int t,n;
int a[N];
signed main()
{
    ios;
    cin>>t;
    while (t--)
    {
        cin>>n;
        for (int i=1;i<=n;i++) cin>>a[i];
        int l=2e9,r=2e9;
        int cnt=0;
        for (int i=1;i<=n;i++)
        {
            int x=a[i];
            if (l>r) swap(l,r);
            if (x<=l) l=x;
            else if (r<x)
            {
                l=x;
                cnt++;
            }
            else r=x;
        }
        cout<<cnt<<endl;
    }
    return 0;
}