Problem Statement

You are given an array of size $$$n$$$ and an integer $$$k$$$. Your task is to remove elements from the array according to the following rules:

• In one move, you must remove exactly three adjacent elements: $$$arr[j]$$$, $$$arr[j+1]$$$, and $$$arr[j+2]$$$.
• These three elements must satisfy: $$$arr[j+1] - arr[j] = k$$$ and $$$arr[j+2] - arr[j+1] = k$$$.

You must perform removals until no more such valid triplets exist. Return the size of the smallest possible array after all possible removals. If the array becomes empty, return $$$-1$$$.

Input

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 10^3$$$). The second line contains $$$n$$$ integers $$$arr_i$$$ ($$$1 \leq arr_i \leq 10^9$$$).

Output

Return a single integer: the size of the smallest possible array.

Examples

Input: n = 10, k = 2 $$$\newline$$$ arr = [2 4 6 8 10 12 8 10 6 8] $$$\newline$$$ Output: 1

Input: n = 6, k = 1 $$$\newline$$$ 12 13 14 15 16 19 Output: 3

Input: n = 9, k = 4 $$$\newline$$$ 1 2 6 10 5 3 7 11 9 Output: -1

I came up with an $$$O(n^3)$$$ iterative DP solution, which gets AC (recursive doesn't, higher overloads maybe). I was wondering, whether an $$$O(n^2)$$$ solution is possible (or provably $$$\Omega(n^3)$$$ for this question)?

Please help in providing an optimised solution (if any)