KMEDIAL - Median of sub-sequences

Let a given sequence S (of length n) of positive integers be called x-medial (where x is a positive integer) if:

  1. n is odd, and the median of the sequence (the ((n+1)/2)th largest term) equals x. OR
  2. n is even, and both the central terms ((n/2)th largest and (n/2+1)th largest) are equal to x.

Given a sequence A (of length N) of positive integers and an integer k, find out how many of its sub-sequences are k-medial.

A sub-sequence of A is any sequence {A[i], A[i+1], A[i+2] ... A[j]}, where 0 ≤ i ≤ j < N.

Input

The first line contains T (T ≤ 15), the number of test cases.

Each test case consists of 2 lines. The first line contains the numbers N (1 ≤ N ≤ 105) and k (1 ≤ k ≤ 109), separated by a single space.

The next line contains the sequence A (N terms, each ≤ 109, separated by single spaces between them).

Output

Output T lines, each containing a single integer, equal to the number of k-medial sub-sequences.

Example

Input:
2
3 5
17 5 2
5 2
1 2 2 3 7

Output:
2
7

Added by:Anil Shanbhag
Date:2013-01-15
Time limit:6s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ASM32-GCC MAWK BC C-CLANG NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET

hide comments
2018-11-07 11:07:08
how to solve the problem if it was subsequence (not necessrely continous) rather than sub-array ?

Last edit: 2018-11-07 16:49:23
2018-03-03 21:14:36 Lovro Puzar
Very nice problem. Previous commenter was mistaken. Sub-sequences are contiguous in this problem so the largest output is O(n^2).

Last edit: 2018-03-03 21:14:47
2017-08-08 00:16:17
Would've been much nicer to count them mod 10^9+7. As it stands, you need bigint as for N=10^5 and all elements = k, the answer is 2^(10^5)-1 which I think is ~30 thousand digits.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.