You are given an array a of length N and an integer k. Your task is to find the number of index pairs (i, j) that satisfy the following conditions:

i < j

k * a[j] * a[i] > max(a[i], a[i+1], ..., a[j])

Input:

N — the length of the array (1 ≤ N ≤ 2 * 10^5) k — an integer (1 ≤ k ≤ 10^4) a[i] ≤ 1e9