P5854 [Template] Cartesian Tree.

Some implementations of this problem may trigger a compiler bug in GCC 15.1 under O2. C++ users are advised to submit with C++14 (GCC9).

Given a permutation $p$ of $1 \sim n$, build its Cartesian tree. That is, build a binary tree that satisfies: 1. The index of each node satisfies the property of a binary search tree. 2. The weight of node $i$ is $p_i$, and the weights satisfy the min-heap property.

The first line contains an integer $n$. The second line contains a permutation $p_{1 \dots n}$.

Let $l_i, r_i$ denote the indices of the left and right children of node $i$ (use $0$ if it does not exist). Output one line with two integers: $\operatorname{xor}_{i = 1}^n i \times (l_i + 1)$ and $\operatorname{xor}_{i = 1}^n i \times (r_i + 1)$.

[Sample Explanation] | $i$ | $l_i$ | $r_i$ | | :-: | :-: | :-: | | $1$ | $0$ | $0$ | | $2$ | $1$ | $4$ | | $3$ | $0$ | $0$ | | $4$ | $3$ | $5$ | | $5$ | $0$ | $0$ | [Constraints] For $30\%$ of the testdata, $n \le 10^3$. For $60\%$ of the testdata, $n \le 10^5$. For $80\%$ of the testdata, $n \le 10^6$. For $90\%$ of the testdata, $n \le 5 \times 10^6$. For $100\%$ of the testdata, $1 \le n \le 10^7$. Translated by ChatGPT 5