#77. 合唱比赛

合唱比赛

附加文件

【题目描述】

有 N 头奶牛排成一排,第 i 头奶牛的身高为 Hi。已知奶牛的身高互不相同,且均为不大于 N 的正整数。奶牛 Bessie 也在队伍当中,她的身高为 M。

Farmer John 要从中选取若干头奶牛参加合唱比赛。由于奶牛 Bessie 是领唱,所以 Bessie 必须参加。因为是合唱比赛,所以不能只让 Bessie 一头牛参加。另外,John 还希望满足:

1、选出的奶牛在原队伍中是连续的(包含 Bessie);

2、选出的奶牛数量为奇数(包含 Bessie);

3、选出的奶牛按身高从低到高排序,Bessie 恰好位于正中间。

问:John 有多少种满足要求的选取方案?

【输入格式】

第一行:包含两个整数 N, M

第二行:包含 N 个整数 Hi,数据保证 Hi 互不相同。

【输出格式】

一个整数,表示方案数

【样例输入】

5 3
1 3 2 4 5

【样例输出】

2

【样例解释】

{3,2,4},{1,3,2,4,5}

【数据规模】

全部测试点满足:N100000,1Hi,MNN ≤ 100000, 1 ≤ Hi, M ≤ N。具体地:

测试点 1-3:1N1001 ≤ N ≤ 100

测试点 4-5:1N1031 ≤ N ≤ 10^3

测试点 6-7:1N1041 ≤ N ≤ 10^4

测试点 8-12:1N1051 ≤ N ≤ 10^5