All problems

Detecting the Convergence Point

mediumPythonGradient Descent

A finished training run at Kestrel Freight is one where the dial has stopped moving, and "stopped" needs a number attached to it, because a run never settles exactly — it creeps by smaller and smaller amounts forever. The team's rule is a tolerance: once a move changes the dial by less than that tolerance, the run has converged and the remaining epochs were wasted electricity. The reviewer wants the first such move, so the trainer can be told to stop there next time; what happens after it is not interesting, even if the dial twitches again.

Task: Print which move first changed the dial by less than the tolerance.

Input

The first line holds two numbers separated by a single space: n, the count of values logged, and the tolerance. The second line holds n numbers separated by single spaces: the dial's starting value, then its value after each move, in order. So n values describe n - 1 moves.

Output

One line. If some move changed the dial by less than the tolerance, print the number of the earliest such move, counting the first move as 1 — a change is measured as the size of the difference between a value and the one before it, so a move down counts the same as a move up. If no move qualifies, print exactly no convergence. A change of exactly the tolerance does not qualify.

Example:

Input:
4 0.5
10 6 6 6

Output:
2

Sign in to solve this problem

Reading problems is free for everyone — solving them (Run, Submit, and tracking what you've solved) needs an account.

Sign in

Discussion

Sign in to join the discussion — reading is open to everyone.

Loading comments…