枚举 · 例9-中位数图
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}本题转译自 [CQOI 2009] 中位数。
\hspace{15pt}给出 1 \sim n 的一个排列^{\texttt{[1]}},统计该排列有多少个长度为奇数的子序列^{\texttt{[2]}}中位数^{\texttt{[3]}}b

\hspace{15pt}长度为 n排列^{\texttt{[1]}}是由 1 \sim nn 个整数、按任意顺序组成的数组,其中每个整数恰好出现一次。例如,\{2,3,1,5,4\} 是一个长度为 5 的排列,而 \{1,2,2\}\{1,3,4\} 都不是排列,因为前者存在重复元素,后者包含了超出范围的数。
\hspace{15pt}子序列^{\texttt{[2]}}为从原数组中删除任意个(可以为零、可以为全部)元素得到的新数组。
\hspace{15pt}长度为 n 的数组 \{a_1,a_2,\cdots,a_n\} ,其中位数^{\texttt{[3]}}为将所有元素从小到大排列后,位于中间的数。例如,数组 \{2,3,1,5,4\} 的中位数是 3 ,而数组 \{1,2,3\} 的中位数是 2

输入描述:

\hspace{15pt}第一行输入两个整数 n,b \left(1 \leqq b \leqq n \leqq 10^5\right) 代表排列长度、目标中位数。
\hspace{15pt}第二行输入 n 个互不相同的整数 a_1,a_2,\cdots,a_n \left(1 \leqq a_i \leqq n\right) 代表排列元素。

输出描述:

\hspace{15pt}在一行上输出一个整数,代表中位数为 b 的奇数长度子序列个数。
示例1

输入

复制
5 3
1 3 2 5 4

输出

复制
3

说明

\hspace{15pt}在这个样例中,长度为奇数、且不为 1 的子序列有:
\hspace{23pt}\bullet\,\{1,3,2\} ,中位数为 2
\hspace{23pt}\bullet\,\{3,2,5\} ,中位数为 3
\hspace{23pt}\bullet\,\{2,5,4\} ,中位数为 4
\hspace{23pt}\bullet\,\{1,3,2,5,4\} ,中位数为 3
\hspace{15pt}别忘了要加上长度为 1 的子序列。因此,中位数为 3 的奇数长度子序列有 3 个,分别是 \{3\}\{3,2,5\}\{1,3,2,5,4\}
示例2

输入

复制
7 4
5 7 2 4 3 1 6

输出

复制
4