13851385 SUSTech Online Judge
Problem 1385 --Heap Process [Easy ll]

1385: Heap Process [Easy ll]

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 515  Solved: 217
[Submit][Status][Web Board]

Description

      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?

Input

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.

Output

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).

Sample Input

3
2
2 1
1
3
1 2 3
2
5
3 1 2 2 3
4

Sample Output

1 1
2 2
3 2

HINT


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).

Source

 

[Submit][Status]