Initially the list content is [1,2,3,...,n]. In each step, you extract the first two elements of the list and insert them at the end of the list in reverse order. What is the first element of the list after k steps?
For example when n=4 and k=3, the list changes as follows:
[1,2,3,4] \rightarrow [3,4,2,1] \rightarrow [2,1,4,3] \rightarrow [4,3,1,2]
Thus, in this case, the first element is 4.
You may assume that n is in the range 2 \dots 10^5 and that k is at most 10^5. The goal is an algorithm with time complexity O(n+k).
In a file fliptwo.py, implement a function solve that returns the first element after k steps.
def solve(n,k):
# TODO
if __name__ == "__main__":
print(solve(4,3)) # 4
print(solve(12,5)) # 11
print(solve(99,555)) # 11
print(solve(12345,54321)) # 9875
Extra challenge: It is actually possible to solve the problem in O(1) time. Feel free to consider such a solution too.