algorithm - Jumping to next closest element -

given array of n elements, numbered 1 n. ith element has value v[i]. elements distinct.

to move ith jth element need spend cost of |i-j|. can jump ith jth element if :

1. j not closer k positions key (i.e. j should not in range [ i-k+1, i+k-1 ]).

2. v[j] < v[i].

each element may have 0 or more elements can jumped to.

we need find summation of cost required go each element closest element can jumped after it. if there no next element can jump element i, consider cost 0.

example : let n=5 , k=1 , array [3,5,4,2,1] here answer 6

explanation :

the next jumping elements for: 1 { }. closest=none, cost = 0 2 { 1 }. closest=1, cost = 1 3 { 1 , 2 }. closest=2, cost = 3 4 { 1 , 2 , 3 }. closest=2, cost= 1 5 { 1 , 2 , 3 , 4 }. closest=3 or 4, cost = 1 

total cost 6

i know brute solution run in o(n^2). 1 <= n <= 2 * 10^5 , 1 <= k,v[i] <= n. can better way solve problem ?

by using binary tree store indexes can reduce o(n^2) o(n^lg(n)).

start empty tree t, iterate 1 -> n. on each step, when enter new index in tree, can closest index.