7898 - 试题I:完美子串 25'

通过次数

70

提交次数

225

时间限制 : 1 秒
内存限制 : 256 MB

给定一个n个数的正整数序列A_1,A_2,...,A_n以及数字x,现在JM想从中找出一个完美子串。

对于完美子串必须满足如下条件:

  1. 该子串为整数序列中连续的一段数字.
  2. 该子串一定包含数字x
  3. 该子串区间内大于x的数字和小于x的数字的个数一样多。

现在JM想知道,他总共有多少种不同的选择方案。

注意:对于两种方案,只要对应区间不相同则视为不同的选择方案。

输入

第一行输入两个正整数n,x,含义如题目描述

第二行输入n个正整数a_i

输出

输出一个整数,表示不同的选择方案数。

样例

输入

5 4
1 2 3 4 5

输出

2

输入

7 5
6 9 3 5 3 2 9

输出

4

提示

样例2解释

{5},{9,3,5},{6,9,3,5,3},{6,9,3,5,3,2,9}

数据范围

对于 30\%的数据有:N<=100

对于 70\%的数据有: N<=10000

对于 100\%的数据有: N<=100000, a_i <= 10^9,数据保证数字x只出现一次

来源

竞码编程-蓝桥杯模拟赛6(大学生组&青少年组)