← 返回题目列表

Codeforces · 1005/E1

E1. 线段中值(排列版)

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

You are given a permutation $$$p_1, p_2, \dots, p_n$$$.长度 $$$n$$$ 的排列是一个序列,使得 $$$1$$$ 和 $$$n$$$ 之间的每个整数在序列中恰好出现一次。

Find the number of pairs of indices $$$(l, r)$$$ ($$$1 \le l \le r \le n$$$) such that the value of the median of $$$p_l, p_{l+1}, \dots, p_r$$$ is exactly the given number $$$m$$$.

序列的中位数是按非降序排序后位于序列中间的元素的值。 If the length of the sequence is even, the left of two middle elements is used.

For example, if $$$a=[4, 2, 7, 5]$$$ then its median is $$$4$$$ since after sorting the sequence, it will look like $$$[2, 4, 5, 7]$$$ and the left of two middle elements is equal to $$$4$$$. $$$[7, 1, 2, 9, 6]$$$ 的中位数等于 $$$6$$$,因为排序后,值 $$$6$$$ 将位于序列的中间。

编写一个程序来查找索引对 $$$(l, r)$$$ ($$$1 \le l \le r \le n$$$) 的数量,使得 $$$p_l, p_{l+1}, \dots, p_r$$$ 的中值恰好是给定的数字 $$$m$$$。

输入

The first line contains integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2\cdot10^5$$$, $$$1 \le m \le n$$$) — the length of the given sequence and the required value of the median.

第二行包含排列 $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$)。 Each integer between $$$1$$$ and $$$n$$$ occurs in $$$p$$$ exactly once.

输出

打印所需的号码。

示例

输入 #1

5 4
2 4 5 3 1

输出 #1

4

输入 #2

5 5
1 2 3 4 5

输出 #2

1

输入 #3

15 8
1 15 2 14 3 13 4 8 12 5 11 6 10 7 9

输出 #3

48

注意

在第一个示例中,合适的索引对是:$$$(1, 3)$$$、$$$(2, 2)$$$、$$$(2, 3)$$$ 和 $$$(2, 4)$$$。