CF2178E Flatten or Concatenate

This is an interactive problem. While procrastinating at work, Dilhan the elf stumbled upon two arrays $ a $ and $ b $ . Initially, both of them consist of a single integer $ 2^k $ (i.e., $ a=b=[2^k] $ ), where $ k $ is a non-negative integer. Dilhan then applied the following two types of operations an arbitrary number of times (possibly zero), in any order: 1. Flatten — Choose either $ a $ or $ b $ , and select any element $ x $ that is maximal within that array ( $ x $ does not need to be maximal in the other array). Then, replace $ x $ with two copies of $ \frac x2 $ in the same position. This operation can only be applied if $ x $ is even. 2. Concatenate — Set both $ a $ and $ b $ to be $ a+b $ , where $ + $ denotes array concatenation. After performing these operations, Dilhan discards $ b $ , hides $ a $ from you, and challenges you to a game. Let $ n $ be the length of the hidden array $ a $ . You may make the following query: - Choose an interval $ [l, r] $ ( $ 1\le l\le r\le n $ ), and Dilhan will tell you the sum $ a_l+a_{l+1}+\cdots+a_r $ . Determine the value of the maximum element of $ a $ by making at most $ 300 $ queries.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 100 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 10^5 $ ) — the length of $ a $ . It is guaranteed that $ 1\le a_i\le 2^{30} $ , and the array $ a $ can be generated by the process described in the statements. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

N/A

In the first test case, Dilhan's hidden array $ a $ is $ [1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 2] $ . It can be generated by the following process: \#Type $ a $ after operation $ b $ after operation0 $ [4] $ $ [4] $ 1Flatten $ a $ $ [\underline 4] \to {[2, 2]} $ $ [4] $ 2Flatten $ b $ $ [2, 2] $ $ [\underline 4] \to {[2, 2]} $ 3Flatten $ a $ $ [2, \underline 2] \to {[2, 1, 1]} $ $ [2, 2] $ 4Concatenate $ [2, 1, 1, 2, 2] $ $ [2, 1, 1, 2, 2] $ 5Flatten $ a $ $ [\underline 2, 1, 1, 2, 2]\to {[1, 1, 1, 1, 2, 2]} $ $ [2, 1, 1, 2, 2] $ 6Concatenate $ [1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 2] $ $ [1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 2] $ - For the query $ \mathtt{?\;3\;8} $ , the jury responded with $ 1+1+2+2+2+1=9 $ ; - For the query $ \mathtt{?\;1\;4} $ , the jury responded with $ 1+1+1+1=4 $ ; - For the query $ \mathtt{?\;5\;11} $ , the jury responded with $ 2+2+2+1+1+2+2=12 $ . And the value of the maximum element of $ a $ is $ 2 $ . In the second test case, the array $ a $ has only one element. By the query, the value of the only element is $ 1 $ , and it must also be the maximum value. In the third test case, Dilhan's hidden array $ a $ is $ [4, 4, 4, 4, 4, 4, 4, 4] $ . It can be generated by the following process: \#Type $ a $ after operation $ b $ after operation0 $ [4] $ $ [4] $ 1Concatenate $ [4, 4] $ $ [4, 4] $ 2Concatenate $ [4, 4, 4, 4] $ $ [4, 4, 4, 4] $ 3Concatenate $ [4, 4, 4, 4, 4, 4, 4, 4] $ $ [4, 4, 4, 4, 4, 4, 4, 4] $ And the value of the maximum element of $ a $ is $ 4 $ . In the fourth test case, Dilhan's hidden array $ a $ is $ [2^{29}, 2^{29}, 2^{30}, 2^{29}, 2^{28}, 2^{28}, 2^{29}, 2^{29}] $ .