Given an integer array nums, find number of distinct contiguous subarrays with at most k odd elements. Two subarrays are distinct when they have at least one different element.

I was able to do it in O(n^2). But need solution for O(nlogn).

Example 1:

```
Input: nums = [3, 2, 3, 4], k = 1
Output: 7 
Explanation: [3], [2], [4], [3, 2], [2, 3], [3, 4], [2, 3, 4]
Note we did not count [3, 2, 3] since it has more than k odd elements.

```

Example 2:

```
Input: nums = [1, 3, 9, 5], k = 2
Output: 7
Explanation: [1], [3], [9], [5], [1, 3], [3, 9], [9, 5]

```

Example 3:

```
Input: nums = [3, 2, 3, 2], k = 1
Output: 5
Explanation: [3], [2], [3, 2], [2, 3], [2, 3, 2]
[3], [2], [3, 2] - duplicates
[3, 2, 3], [3, 2, 3, 2] - more than k odd elements

```

Example 4:

```
Input: nums = [2, 2, 5, 6, 9, 2, 11, 9, 2, 11, 12], k = 1
Output: 18

```