Enemy Charlie

Iftekhar_Hakim CUET CSE Fest 2022 - Inte...
Limits 1s, 256 MB

Alice and Bob have stopped playing games. They became friends again. They both agreed that MM 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 MM 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 MM, the array must be their favorite.

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

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

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

Input

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

Second line of input will have NN space-separated integers, denoting the array AA as A1A_1, A2A_2,\dots, ANA_N (1AiN)(1\le A_i \le N).

Output

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

Samples

InputOutput
5 1
1 2 3 4 5
15
InputOutput
12 4
6 1 1 2 2 3 4 5 5 6 6 1
20

Submit

Login to submit.

Statistics

71% Solution Ratio
niaj_pialEarliest, 1M ago
Zobayer_AbedinFastest, 0.0s
S_SubrataLightest, 5.6 MB
Zobayer_AbedinShortest, 1067B
Toph uses cookies. By continuing you agree to our Cookie Policy.