SP13362 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

The first line contains T (T Each test case consists of 2 lines. The first line contains the numbers N (1 The next line contains the sequence A (N terms, each

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