You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

cyx 仰慕 rainboy 跌宕起伏的 rating 变化线。

题目描述

cyx 最近打了 $n$ 场 czoj，其 performance 分别为 $a_1,a_2,\dots,a_n$。为了学习 rainboy 上上下下的 rating 变化风格，他规定一次 performance 是优美的当且仅当这一次和相邻的两次 performance（记为 $a_{i-1},a_i,a_{i+1}$）满足峰形或者谷形。形式化地，$(a_{i-1}-a_i)(a_{i+1}-a_i)>0$。注意，第一次和最后一次的 performance 永远不是优美的。

cyx 作为 czoj 管理员可以决定将一些比赛记录隐藏，剩下一个非空子序列使得序列中“优美的”performance 个数恰好在区间 $[l,r]$ 之间，且相邻两次 performance 不相同。cyx 想知道有多少本质不同的子序列满足条件。

再次提醒，要求相邻两次 performance 不相同。

答案需要对 $99\bf{3}$ $244\ \bf{8}$$53$ 取模。

输入格式

本题单个测试点内有多组数据。

第一行一个整数 $T$，表示数据组数。

接下来的 $T$ 组数据，每组第一行三个非负整数 $n,l,r$，第二行 $n$ 个正整数 $a_i$ 表示 performance 序列。

输出格式

对于每组测试数据，输出一个取模过的整数表示答案。

样例

4
3 0 1
1 2 1
4 0 0
1 4 2 3
6 1 1
1 3 4 2 5 3
10 1 3
5 2 8 8 4 2 2 9 1 4

5
11
20
151

对于第一组测试数据，可以保留子序列 $\{1\}$，$\{2\}$，$\{1,2\}$，$\{2,1\}$。这些子序列都不存在优美的 performance。也可以保留子序列 $\{1,2,1\}$，恰有 $1$ 个 performance （$a_2=2$）是优美的，也满足条件。

数据规模与约定

本题采用捆绑测试。各子任务时限不同。

• Subtask 0（3 pts）：时限 $\text{2s}$，$a_i$ 单调递增。
• Subtask 1（5 pts）：时限 $\text{0.5s}$，$n \leq 15$。
• Subtask 2（25 pts）：时限 $\text{0.5s}$，$n \leq 300$。
• Subtask 3（19 pts）：时限 $\text{5s}$，$a_i$ 互不相同。
• Subtask 4（9 pts）：时限 $\text{5s}$，存在 $1\le p\le n$ 使得 $a_1<a_2<\dots<a_{p-1}<a_n<a_{n-1}<\dots<a_p$。
• Subtask 5（39 pts）：时限 $\text{5s}$，无特殊限制。

对于 $100\%$ 的数据，保证 $2 \leq n \leq 5000$，$0 \leq l\leq r\leq \min(n-2,100)$，$1\le a_i\le10^9$，$1\le T\le5$。

注意：时限很大不意味着可以为所欲为！其实是出题人丑陋的【数据删除】算法常数过大，但是又想放掉。 如果还觉得卡常，那么你有什么实力啊，菜就多练改进算法吧。