Binary and Ternary Search Game 3

Time limit2sMemory limit256 MB

Summary

For each query N, compute the maximum number of array elements compared in binary search and in ternary search over all positions in a sorted array of size N.

Level: Medium7 of 10
Topics: Binary search, Divide and conquer, Recursion, Math
Solved: No attempts yet

Problem

Seojun is playing algorithm games with his father again today. Seojun plays binary search, and his father plays ternary search.

There is an array A of size N, sorted in ascending order, containing distinct integers. When searching for the i-th element A_i of array A with binary search and ternary search, let B_i and T_i be the number of elements of array A that must be referenced before finding A_i, respectively. Seojun received Q queries from his father, each asking him to print the maximum values of B_i and T_i on one line, separated by a space. Help Seojun, who is struggling because N and Q are large.

The pseudocode of the binary search algorithm on an array of size N is as follows.

binary_search(A[0..N-1], value, left, right) {
    mid = (left + right) / 2
    if (A[mid] == value)
        return mid
    else if (value < A[mid])
        return binary_search(A, value, left, mid - 1)
    else
        return binary_search(A, value, mid + 1, right)
}

The pseudocode of the ternary search algorithm on an array of size N is as follows.

ternary_search(A[0..N-1], value, left, right) {
    left_third = left + (right - left) / 3
    right_third = right - (right - left) / 3
    if (A[left_third] == value) 
        return left_third
    else if (A[right_third] == value)
        return right_third
    else if (value < A[left_third])
        return ternary_search(A, value, left, left_third - 1)
    else if (value < A[right_third])
        return ternary_search(A, value, left_third + 1, right_third - 1)
    else
        return ternary_search(A, value, right_third + 1, right)
}

Input

The first line gives the number of queries Q (1 ≤ Q ≤ 500,000). From the second line to the (Q + 1)-th line, the size N of array A is given.

Output

For each query from the first to the Q-th, print the result of that query on its own line.

Constraints

1 ≤ N ≤ 2^63 − 1
1 ≤ Q ≤ 500,000

Examples1

Example 1
Input
```
1
5
```
Expected output
```
2 2
```