Initially, there are n nodes, with index 1, 2, 3, ..., n. Every nodes has a value ai. They enter the tree in order and make the tree as a Max Heap(same value will not swap). This process can make biggest value node to reach the top. After n nodes enter the tree, David wants to find a node with index p. Could you please tell him the node's position with level x, and the index y on that level?
The first line contains an integer \(T(1 \leq T \leq 10)\), indicating the test cases. In each test case, the first line contains an integer \(n(1\leq n\leq 10^5)\). The second line contains n integers, \(a_1, a_2, a_3, ..., a_n (1 \leq a_i \leq 10^9)\) indicating the node's value. The third line contains an integer, indicating the node’s index.
For each test case, please print the level x and index in that level y in one line. Note that, the root position is (1, 1).
For the second test case. Initially, 1 is enter (1, 1). When 2 arrive, it is on (2, 1), but it is bigger than 1, so, 1 and 2 swap. Then, 2 is in (1, 1), 1 is in (2, 1). When 3 arrive, it is on (2, 2), but it is bigger than 2, so, 2 and 3 swap. Then, 3 is in (1, 1), 2 is in (2, 2).