算法一

Subtask $0$：若 $l=0$ 输出 $2^n-1$，否则输出 $0$。期望得分 $3$。

Subtask $4$：观察到最大的优美点个数不超过 $1$，所以胡乱讨论一番应该就过了。期望得分 $9$。

期望得分 $12$。

算法二

以下记 $k=r$，因为好看。

观察到“本质不同”很难做，考虑 $a_i$ 互不相同。我们直接 dp。$f_{i,j,0/1}$ 表示当前凑了 $i$ 个优美点，最后一个数是 $a_j$，最后一处是上升还是下降的方案数。朴素转移，复杂度 $\mathcal O(Tn^2k)$，还不能解决“本质不同”，啥都过不去。结合算法一，期望得分还是 $12$。

算法三

“本质不同”和“复杂度高”至少得解决一个才有更多分！复杂度高是容易解决的。考虑前缀和优化，但是发现转移依赖值域，那就 BIT。需要先对值域离散化，复杂度 $\mathcal O(Tnk\log n)$。不用结合算法一，期望得分 $31$。

算法四

Subtask $1$ 枚举一下子序列，要么哈希要么直接把 vector 扔 set 里面解决本质不同，$\mathcal O(T2^npoly(n))$，结合算法三，期望得分 $36$。

算法五

考虑解决“本质不同”。经典优化：如果有多个满足条件的转移点，我们只取最后一个。然后如果你想不到怎么优化，暴力转移，复杂度是 $\mathcal O(Tn^2k)$，结合算法三，期望得分 $61$。

算法六

想到上个主席树优化它，因为解决本质不同需要在时间轴上查询值域线段树。直接做大概能过，但是不需要。

考虑对于每个不同的值域，直接在得到 dp 值时记录此时的答案，这样就不需要时间轴了，一颗 BIT 搞定，时间复杂度 $\mathcal O(Tnk\log n)$。期望得分 $100$。出题人不卡常的 BIT 跑了 $1.5$s，所以不卡常。但是因为不会 BIT 一开始写的线段树要跑四五秒，怎么回事呢。

小心模数。BIT 是贺的，线段树上改的，所以很丑。

#include<bits/stdc++.h>
#define MOD         993244853
#define int         long long
#define pii         pair<int,int>
#define all(v)      v.begin(),v.end()
#define pb          push_back
#define REP(i,b,e)  for(int i=(b);i<(e);++i)
#define over(x)     {cout<<x<<endl;return;}
using namespace std;
int read(){
	char c=getchar();int res=0;
	while((c<48||c>57)&&c!='-')c=getchar();
	do res=(res<<1)+(res<<3)+(c^48),c=getchar();while(c>=48&&c<=57);
	return res;
}
int num;
struct BIT{
	int c[100005];
	void build(){
		REP(i,0,num+1)c[i]=0;
	}
	void add(int pos,int val){
		++pos;
		while(pos<=num){
			c[pos]+=val;
			pos+=pos&(-pos);
		}
	}
	int query(int l,int r){
		int res=0;
		++r;
		while(r)res+=c[r],r-=r&(-r);
		while(l)res-=c[l],l-=l&(-l);
		return (res%MOD+MOD)%MOD;
	}
}s[105][3];
int n,k,L;
int a[10005];
int lst[10005][105][3][2],vis[10005];
void Main() {
	n=read();L=read();k=read();
	vector<int>_;
	REP(i,0,n)_.pb(a[i]=read());
	sort(all(_));_.erase(unique(all(_)),_.end());
	REP(i,0,n)a[i]=lower_bound(all(_),a[i])-_.begin();
	num=_.size();
	REP(i,0,k+1)REP(j,0,3)s[i][j].build();
	memset(vis,0,sizeof(vis));memset(lst,0,sizeof(lst));
	REP(i,0,n){
		REP(j,0,k){
			int x=(a[i]==0? 0:s[j][1].query(0,a[i]-1))-lst[a[i]][j][1][0];
			s[j+1][0].add(a[i],(x+MOD)%MOD);
			x=(a[i]==num-1? 0:s[j][0].query(a[i]+1,num-1))-lst[a[i]][j][0][1];
			s[j+1][1].add(a[i],(x+MOD)%MOD);
		}
		REP(j,0,k+1){
			int x=(a[i]==0? 0:s[j][0].query(0,a[i]-1)+s[j][2].query(0,a[i]-1));
			s[j][0].add(a[i],(x+MOD*2-lst[a[i]][j][0][0]-lst[a[i]][j][2][0])%MOD);
			x=(a[i]==num-1? 0:s[j][1].query(a[i]+1,num-1)+s[j][2].query(a[i]+1,num-1));
			s[j][1].add(a[i],(x+MOD*2-lst[a[i]][j][1][1]-lst[a[i]][j][2][1])%MOD);
		}
		if(!vis[a[i]])s[0][2].add(a[i],1),vis[a[i]]=1;
		REP(j,0,k+1){
			REP(l,0,3)lst[a[i]][j][l][0]=(a[i]==0? 0:s[j][l].query(0,a[i]-1));
			REP(l,0,3)lst[a[i]][j][l][1]=(a[i]==num-1? 0:s[j][l].query(a[i]+1,num-1));
		}
	}
	int ans=0;
	REP(i,L,k+1)REP(j,0,3)(ans+=s[i][j].query(0,num-1))%=MOD;
	printf("%lld\n",ans);
}
void TC() {
	int tc=read();
	REP(i,0,tc){
		Main();
		cout.flush();
	}
}
signed main() {
	return cin.tie(0),cout.tie(0),ios::sync_with_stdio(0),TC(),0;
}
/*
1. CLEAR the arrays (ESPECIALLY multitests)
2. DELETE useless output
 */