START201——Delete Maximum（计数问题最重要的就是找到一个特征） · znzryb
## 思路讲解
通过打表，我们发现这个通过最大值和这个长度，我们可以唯一确定一个序列。
```cpp
最大值为：1 的长度为：1 的东西：1
最大值为：2 的长度为：1 的东西：1
最大值为：2 的长度为：2 的东西：1
最大值为：3 的长度为：1 的东西：1
最大值为：3 的长度为：2 的东西：1
最大值为：3 的长度为：3 的东西：1
最大值为：4 的长度为：1 的东西：1
最大值为：4 的长度为：2 的东西：1
最大值为：4 的长度为：3 的东西：1
最大值为：4 的长度为：4 的东西：1
最大值为：5 的长度为：1 的东西：1
最大值为：5 的长度为：2 的东西：1
最大值为：5 的长度为：3 的东西：1
最大值为：5 的长度为：4 的东西：1
最大值为：5 的长度为：5 的东西：1
最大值为：6 的长度为：1 的东西：1
最大值为：6 的长度为：2 的东西：1
最大值为：6 的长度为：3 的东西：1
最大值为：6 的长度为：4 的东西：1
最大值为：6 的长度为：5 的东西：1
最大值为：6 的长度为：6 的东西：1
最大值为：7 的长度为：1 的东西：1
最大值为：7 的长度为：2 的东西：1
最大值为：7 的长度为：3 的东西：1
最大值为：7 的长度为：4 的东西：1
最大值为：7 的长度为：5 的东西：1
最大值为：7 的长度为：6 的东西：1
最大值为：7 的长度为：7 的东西：1
最大值为：8 的长度为：1 的东西：1
最大值为：8 的长度为：2 的东西：1
最大值为：8 的长度为：3 的东西：1
最大值为：8 的长度为：4 的东西：1
最大值为：8 的长度为：5 的东西：1
最大值为：8 的长度为：6 的东西：1
最大值为：8 的长度为：7 的东西：1
最大值为：8 的长度为：8 的东西：1
最大值为：9 的长度为：1 的东西：1
最大值为：9 的长度为：2 的东西：1
最大值为：9 的长度为：3 的东西：1
最大值为：9 的长度为：4 的东西：1
最大值为：9 的长度为：5 的东西：1
最大值为：9 的长度为：6 的东西：1
最大值为：9 的长度为：7 的东西：1
最大值为：9 的长度为：8 的东西：1
最大值为：9 的长度为：9 的东西：1
最大值为：10 的长度为：1 的东西：1
最大值为：10 的长度为：2 的东西：1
最大值为：10 的长度为：3 的东西：1
最大值为：10 的长度为：4 的东西：1
最大值为：10 的长度为：5 的东西：1
最大值为：10 的长度为：6 的东西：1
最大值为：10 的长度为：7 的东西：1
最大值为：10 的长度为：8 的东西：1
最大值为：10 的长度为：9 的东西：1
最大值为：10 的长度为：10 的东西：1
最大值为：11 的长度为：1 的东西：1
最大值为：11 的长度为：2 的东西：1
最大值为：11 的长度为：3 的东西：1
最大值为：11 的长度为：4 的东西：1
最大值为：11 的长度为：5 的东西：1
最大值为：11 的长度为：6 的东西：1
最大值为：11 的长度为：7 的东西：1
最大值为：11 的长度为：8 的东西：1
最大值为：11 的长度为：9 的东西：1
最大值为：11 的长度为：10 的东西：1
最大值为：11 的长度为：11 的东西：1
```
如果说是一个递增的一个序列，我们可以得到任何长度的序列（不大于本身值）。但是如果序列发生变化，就不行了。
```cpp
最大值为：11 的长度为：1 的东西：1
最大值为：11 的长度为：2 的东西：1
最大值为：11 的长度为：3 的东西：1
最大值为：11 的长度为：4 的东西：1
最大值为：11 的长度为：5 的东西：1
最大值为：11 的长度为：6 的东西：1
最大值为：11 的长度为：7 的东西：1
最大值为：11 的长度为：8 的东西：1
最大值为：11 的长度为：9 的东西：1
最大值为：11 的长度为：10 的东西：1
最大值为：11 的长度为：11 的东西：1
```
## AC代码
[https://www.codechef.com/viewsolution/1191801507](https://www.codechef.com/viewsolution/1191801507)
::: 源代码
```cpp
// by Gospel_rock
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())
using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) { cerr << x; }
// 可以打印多层数组，但是格式不是很好
template<typename T> void _print(vector<T> v) { cerr << "[ "; for (T i : v) _print(i), cerr << " "; cerr << "]"; }
template<typename T> void _print(set<T> s) { cerr << "{ "; for (T i : s) _print(i), cerr << " "; cerr << "}"; }
template<typename T, typename U> void _print(pair<T, U> p) { cerr << "{"; _print(p.first); cerr << ", "; _print(p.second); cerr << "}"; }
template<typename T, typename U> void _print(map<T, U> m) { cerr << "{ "; for (auto &p : m) _print(p), cerr << " "; cerr << "}"; }
// 打印两层数组，格式好一些
template<typename T> void _print(vector<vector<T>> v){cerr<<"{\n";for (auto i : v) _print(i), cerr << "\n";cerr<<" }";}
#endif
using ll = long long;using ull = unsigned long long;
using ld=double;using LD=long double;
using i128 = __int128;
using pdd = pair<ld,ld>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<ld>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)2e5+10,INF=(ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod=998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;
inline void __();
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>lT;
while(lT--)
__();
return 0;
}
/*
通过打表，我们发现这个通过最大值和这个长度，我们可以唯一确定一个序列。
*/
ll Pos[MAXN];
inline void __(){
cin>>N;
vll A(N+5);
FOR(i,1,N){
cin>>A[i];
Pos[A[i]]=i;
}
ll id=max(A[1],A[N]);
ll ans=0;
// 通过打表，我们发现这个通过最大值和这个长度，我们可以唯一确定一个序列。
vll pre(N+5,INF),suf(N+5,INF);
FOR(i,1,N){
pre[i]=min(pre[i-1],A[i]);
}
ROF(i,N,1){
suf[i]=min(suf[i+1],A[i]);
}
FOR(i,1,N){
if(i==N){
// 如果说这个 i 是 N，在中间的话就就会直接被删掉
if(Pos[i]==1 || Pos[i]==N){
ans+=N;
}else{
ans++;
}
continue;
}
if(i==1 || i==2){
ans+=i;
continue;
}
if(i<=suf[Pos[i]] || i<=pre[Pos[i]]){
ans+=i;
}else{
ans++;
}
}
ans%=mod;
cout<<ans<<"\n";
// ROF(i,N,1){
// if(Pos[i]==1 && Pos[i]==N){
// id=i;
// break;
// }
// }
}
/*
AC
https://www.codechef.com/viewsolution/1191801507
1
4
1 3 2 4
[ 1 ]: 2
[ 1 2 ]: 1
[ 2 ]: 1
[ 3 ]: 1
[ 3 1 ]: 1
[ 3 1 2 ]: 1
[ 3 1 4 2 ]: 1
最大值为：1 的长度为：1 的东西：1
最大值为：2 的长度为：1 的东西：1
最大值为：2 的长度为：2 的东西：1
最大值为：3 的长度为：1 的东西：1
最大值为：3 的长度为：2 的东西：1
最大值为：3 的长度为：3 的东西：1
最大值为：4 的长度为：4 的东西：1
*/
```
:::
## 心路历程（WA，TLE，MLE……）