During the festive Diwali celebration, Neha received an abundance of sweets and decided to share them with the needy children in her community. There were N children, each numbered from 1 to N, and each child had a specific request for sweets - child i wanted at least cᵢ boxes. The children stood in a line according to their numbers, eagerly waiting for their turn.
Neha had a plan for distributing the sweets: she would give K boxes to the child at the front of the line. If that child hadn’t received enough boxes yet, they would go to the back of the line; if they had received enough, they would go home happily.
Neha repeated this process until all the children received their required sweets. Now, Neha is curious to find out which child will receive the last box of sweets. Can you help her determine the number of that child?
The second line of the input contains N space-separated integers.
Constraints:
1 ≤ N ≤ 105
1 ≤ ci ≤ 109
1 ≤ K ≤ 109
5 2
1 3 1 4 2
Sample Output
4