Recover the Password

A secret password is stored as a sequence of n distinct non-negative integers \(a_1, a_2, \ldots, a_n\). You do not know the sequence. Instead, you are given access to two types of queries on the sequence (where the sequence indices start at 1):

• Range Query: Given indices \(l\) and \(r\) (with \(1 \le l \le r \le n\)), you receive the value \[ \left(\sum_{k=l}^{r} a_k\right) - \left(\min_{k=l}^{r} a_k\right). \]</p>
• Point Query: Given an index \(k\) (with \(1 \le k \le n\)), you receive the value \(a_k\). This query type can be used at most twice.

Your goal is to determine the entire password sequence using as few queries as possible. Note that even though the queries use 1-based indexing, when you finally return the answer you must output a vector (or equivalent) that is 0-indexed.

This is an interactive problem. You are required to implement the following function:

#include <cstdint>
#include <vector>

std::vector<uint32_t> recover(int n);

You can use the two provided functions to query the password:

#include <cstdint>

uint64_t query(int l, int r); // Returns \(\left(\sum_{k=l}^{r} a_k\right) - \left(\min_{k=l}^{r} a_k\right)\).
uint32_t get(int x);       // Returns the value of \(a_x\). (Can be used at most 2 times.)

The sample implementation below demonstrates how the interactive library might be used (this is only for illustration; the actual implementation of the library is hidden in lib.cpp):

#include <cstdint>
#include <vector>

uint64_t query(int l, int r);
uint32_t get(int x);

std::vector<uint32_t> recover(int n) {
    std::vector<uint32_t> ans(n);
    // Your code to recover the sequence goes here...
    return ans;
}

You can compile your solution locally using C++11/17 with the command:

g++ -o code code.cpp lib.cpp

Good luck!

inputFormat

The input begins with a single integer n (the length of the password). In the test cases provided for simulation, the next line contains n distinct non-negative integers separated by spaces representing the password sequence.

outputFormat

Output the recovered password as a single line of n space-separated integers. Note that even though the queries are 1-indexed, the returned answer (the vector) should be 0-indexed.

sample

3
1 2 3

1 2 3