This page is still under construction.

Parts of this page are still being built. What you see may change.

Subarray Average of a Sequence

Interview

Time limit1sMemory limit256 MB

Summary
Count the contiguous subarrays of a given sequence whose elements have an average exactly equal to K.
Level

Medium6 of 10

Topics
Prefix sum, Hash map, Array, Math
Solved
No attempts yet

Problem

A sequence A1,A2,⋯ ,ANA_1, A_2, \cdots, A_N of length NN is given. Count the number of intervals whose elements all have an average of exactly KK.

Input

The first line gives the size of the sequence NN and the desired average KK. (1≤N≤200,0001 \le N \le 200,000, −109≤K≤109-10^9 \le K \le 10^9)

The second line gives the sequence A1,A2,⋯ ,ANA_1, A_2, \cdots, A_N. (1≤i≤N1 \le i \le N, −109≤Ai≤109-10^9 \le A_i \le 10^9)

Every number in the input is an integer.

Output

Print the number of intervals whose elements all have an average of KK.

Examples2

  1. Example 1

    Input
    4 2
    1 3 2 2
    
    Expected output
    6
    
  2. Example 2

    Input
    10 3
    2 4 3 1 5 3 2 4 1 3
    
    Expected output
    19