Limits
1s, 256 MB

Alice and Bob have stopped playing games. They became friends again. They both agreed that $M$ is their favorite integer.

Not only favorite integer, they are also agreeing to decide their favorite arrays, strings, geometrical shapes etc. Sometimes things are interrelated. Their favorite integer $M$ has a role to decide their favorite arrays.

To decide whether an array is their favorite, they will multiply the frequencies of every distinct element occurring in that array. Frequency of an element in that array is the number of times the element occurs in that array. If the product is exactly $M$, the array must be their favorite.

For example, if $M=3$, $[1, 2, 4, 4, 5, 4]$ will be one of their favorite arrays. Here they will calculate the product of frequencies of $1$, $2$, $4$ and $5$. It is $1 \times 1 \times 3 \times 1 = 3$. Similarly, if $M=1$, $[1, 2, 3]$ is one of their favorite arrays.

Charlie is acting like their enemy now, he brought an array $A$ of $N$ integers. Alice and Bob must reply how many sub-arrays of it are their favorite. That is, how many pairs of integers $l$ and $r$ exist, such that $1 \le l \le r \le N$ and array $A_l, A_{l+1}, \dots, A_r$ is their favorite.

None of Alice and Bob can do it without your help. Help the friends.

First line of input will have two space-separated integers $N$ $(1\le N \le 10^5)$, that is the size of the Charlie’s array and $M$ $(1\le M \le 10^5)$, their favorite integer.

Second line of input will have $N$ space-separated integers, denoting the array $A$ as $A_1$, $A_2$,$\dots$, $A_N$ $(1\le A_i \le N)$.

In one line, print total number of sub-arrays of $A$ that are their favorite.

Input | Output |
---|---|

5 1 1 2 3 4 5 | 15 |

Input | Output |
---|---|

12 4 6 1 1 2 2 3 4 5 5 6 6 1 | 20 |

Login to submit.

71%
Solution Ratio

niaj_pialEarliest,

Zobayer_AbedinFastest, 0.0s

S_SubrataLightest, 5.6 MB

Zobayer_AbedinShortest, 1067B

Toph uses cookies. By continuing you agree to our Cookie Policy.