思路

先明确「当前行动者是否必胜」的定义。设 $W(i)$ 表示：轮到某人行动、筹码停在第 $i$ 个元素上时，当前行动者是否必胜。题目规定「无法移动者获胜」（反规则），所以：

• 若第 $i$ 个元素没有合法落点（左边没有比它小的元素），则 $W(i)=\text{true}$，无法移动直接获胜；
• 否则 $W(i)=\text{true}$ 当且仅当存在一个合法落点 $j$ 使得 $W(j)=\text{false}$（把必败局面留给对手）。

baba 第一步把筹码放到 $i$，之后轮到 booey 行动，所以第 $i$ 个元素对 baba 是「幸运」的当且仅当 $W(i)=\text{false}$。

关键结论：

$$W(i)=\text{false}\iff\text{以 }i\text{ 结尾的最长严格递增子序列长度恰为 }2$$

对排列做归纳证明：

• 长度 1：左边没有比它小的元素，没有合法落点，$W(i)=\text{true}$；
• 长度 2：任一合法落点 $j$ 都满足 $j<i,\ p_j<p_i$。如果以 $j$ 结尾的 LIS 长度 $\ge2$，接上 $i$ 就得到长度 $\ge3$ 的递增子序列，矛盾；所以每个合法落点 $j$ 的 LIS 长度都是 $1$，即 $W(j)=\text{true}$，不存在 $W(j)=\text{false}$ 的落点，故 $W(i)=\text{false}$；
• 长度 $\ge3$：取一条以 $i$ 结尾、长度为 $L\ge3$ 的递增子序列，记其中第二个元素为 $j$。若以 $j$ 结尾的 LIS 比 $L-1$ 更长，接上这条子序列剩余的元素就会得到比 $L$ 更长的递增子序列，矛盾，所以以 $j$ 结尾的 LIS 长度恰为 $2$；由归纳 $W(j)=\text{false}$，于是 $W(i)=\text{true}$。

因此答案就是「以 $i$ 结尾的 LIS 长度恰为 $2$」的元素个数。

求法： 用经典贪心维护，数组 $b$ 中 $b[0]=0$ 是占位（排列的取值都 $\ge1$），$b[len]$ 表示长度为 $len$ 的严格递增子序列的最小结尾。从左到右处理 $a_i$，在 $b$ 中 lower_bound 找到第一个 $\ge a_i$ 的位置 $pos$：

• 若 $a_i$ 比当前所有结尾都大（走 push 分支），新 LIS 长度为 b.size()-1，等于 $2$ 就计数（例如 $[1,2,3]$ 的第 $2$ 个元素就是走这个分支被计数的）；
• 否则把 $b[pos]$ 替换为 $a_i$，若 $pos==2$ 就计数。

两个分支都要判断，缺一不可。

复杂度： 时间 $O(n\log n)$，空间 $O(n)$。

代码

#include<bits/stdc++.h>
#define int long long
#define dd double
#define str string
#define el cout << '\n'
#define re return
#define ff first
#define ss second
#define pll pair<int,int>
#define pdd pair<dd,dd>
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;

void go(){
    int n;cin>>n;
    // b[0]=0 是占位，b[len] 表示长度为 len 的最长递增子序列的最小结尾
    vector<int>a(n), b = {0};

    for(int i=0;i<n;i++){
        cin>>a[i];
    }

    int ans = 0;
    for(int i=0;i<n;i++){
        int val = a[i];
        if(val > b.back()){
            // 比所有结尾都大，LIS 长度增加
            b.push_back(val);
            if(b.size()==3){         // 新的长度为 2（下标占位后 size 为 3）
                ans++;
            }
        }else{
            // 找到第一个 >= val 的位置并替换，保持结尾尽量小
            int idx = lower_bound(all(b), val) - b.begin();
            if(idx==2){              // 长度为 2 的结尾被更新，说明 LIS 长度恰为 2
                ans++;
            }
            b[idx] = val;
        }

    }

    cout<<ans<<endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int _=1;
    cin >>_;                         // 多组测试数据
    while(_--){
        go();
    }
    return 0;
}