Question
Index After Rotations
Emma has an array of n unique integers arranged in ascending order, and she enjoys experimenting with it. One of her favorite activities is to rotate the array counterclockwise. In each rotation, she moves the last element of the array to the beginning, shifting all other elements one position to the right. After performing this rotation k times, Emma is curious: what will be the new index of the original first element in the rotated array? Can you help her figure out its position?
Input
The input consists of three lines:
The first line of the input contains an integer n - the size of the array.
The second line of the input contains n space-separated integers arr[1], arr[2],. , arr[n] - the elements of the array in ascending order.
The third line contains a single integer k - the number of rotations.
Constraints
1 ≤ n ≤ 105
1 ≤ arr[i] ≤ 109
0 ≤ k ≤ 105
The first line of the input contains an integer n - the size of the array.
The second line of the input contains n space-separated integers arr[1], arr[2],. , arr[n] - the elements of the array in ascending order.
The third line contains a single integer k - the number of rotations.
Constraints
1 ≤ n ≤ 105
1 ≤ arr[i] ≤ 109
0 ≤ k ≤ 105
Output
Print a single integer - the index of the first element from the original array in the rotated array.
Example
Input
5
1 2 3 4 5
2
Output
3
Explanation
In this example, the initial array is [1, 2, 3, 4, 5]. After 2 rotations, the array becomes [4, 5, 1, 2, 3]. The first element of the original array, which is 1, is now at index 3 (1- Based indexed). Therefore, the output is 3.
5
1 2 3 4 5
2
Output
3
Explanation
In this example, the initial array is [1, 2, 3, 4, 5]. After 2 rotations, the array becomes [4, 5, 1, 2, 3]. The first element of the original array, which is 1, is now at index 3 (1- Based indexed). Therefore, the output is 3.