Background

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

Problem Description

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.

Input Format

The first line contains an integer $n$.

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

Output Format

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

5
4 1 3 2 5

19 21

Hint

[Sample Explanation]

[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