1. (Josephus problem) n people numbered from 1 to n sit in a circle and play a game. Starting from the first person and every kth person is eliminated. Write an algorithm that prints out the order in which people are eliminated.
2. (Level ancestor) You are given an tree of size n. ancestor(node, levelsUp) finds the node’s ancestor that is levelsUp steps up. For example, ancestor(node, 1) returns the father and ancestor(node, 2) returns the grandfather. Implement ancestor(node, levelsUp) efficiently. (O(sqrt(n)) per query)

3. (Range median) You are given an array of size n. Implement a data structure to perform update operations a[i] = k and range median operations efficiently. The range median query, median(l, r)  returns the median element of the sorted subsequence a[l..r]. (<tex>O(log n)</tex> per update and <tex>O(sqrt(n) log n)</tex> per query)

3. (Range median) You are given an array of size n. Implement a data structure to perform update operations a[i] = k and range median operations efficiently. The range median query, median(l, r)  returns the median element of the sorted subsequence a[l..r]. (<tex>O(\log n)</tex> per update and <tex>O(\sqrt(n) \log n)</tex> per query)

You can discuss the problems in the comments section.