Вам дан массив a длины N и целое число k. Ваша задача — найти количество пар индексов (i, j), удовлетворяющих следующим условиям:

i < j

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

Входные данные:

N — длина массива (1 ≤ N ≤ 2 * 10^5);

k — целое число (1 ≤ k ≤ 10^4);

a[i] <= 1e9