548. K-Distinct subarrays

0

Hard

A subarray is called **K-Distinct Subarray** if it contains **atmost** **k** distinct elements.

You are given an array of **n** integers and a value **k** , your task is to calculate the number of **K-Distinct subarrays** that have at most **k** distinct values.

You are given an array of **n** integers and a value **k** , your task is to calculate the number of **K-Distinct subarrays** that have at most **k** distinct values.

Input Format

First line contains two space separated integers n and k .

Second line contains an integer array.

Second line contains an integer array.

Output Format

Print total number of K-distinct subarrays.

Example

Input

5 2
1 2 3 1 1

Output

10

Constraints

1 <= k , n <= 10

1 <= arr[i] <= 10

^{5}1 <= arr[i] <= 10

^{9}Loading...

View Submissions

Console