← 返回题目列表

Codeforces · 2064/F

F. 我们正在总结

中文机器翻译题面 查看原题

给定一个长度为 $$$n$$$ 的数组 $$$a$$$ 和一个整数 $$$k$$$。

调用长度为 $$$m$$$ 的非空数组 $$$b$$$ 史诗 如果存在整数 $$$i$$$,其中 $$$1 \le i \lt m$$$ 和 $$$\min(b_1,\ldots,b_i) + \max(b_{i + 1},\ldots,b_m) = k$$$。

计算数量 史诗 $$$a$$$ 的子数组$$$^{\text{*}}$$$。

$$$^{\text{*}}$$$数组 $$$a$$$ 是数组 $$$b$$$ 的子数组,如果 $$$a$$$ 可以通过从 $$$b$$$ 删除开头的几个(可能是零个或全部)元素和从末尾删除几个(可能是零个或全部)元素来获得。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$n \lt k \lt 2 \cdot n$$$) - 数组 $$$a$$$ 和 $$$k$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le n$$$)。

所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出 $$$a$$$ 的史诗连续子数组的数量。

示例

输入
复制

6
5 7
1 2 3 4 5
7 13
6 6 6 6 7 7 7
6 9
4 5 6 6 5 1
5 9
5 5 4 5 5
5 6
3 3 3 3 3
6 8
4 5 4 5 4 5

输出
复制

2
12
3
8
10
4

注意

这些是第一个测试用例中的所有史诗子数组:

  • $$$[2, 3, 4, 5]$$$,因为 $$$\min(2, 3) + \max(4, 5) = 2 + 5 = 7$$$。
  • $$$[3, 4]$$$,因为 $$$\min(3) + \max(4) = 3 + 4 = 7$$$。

在第二个测试用例中,每个包含至少一个 $$$6$$$ 和至少一个 $$$7$$$ 的子数组都是史诗级的。