【模板】笛卡尔树

题目背景

本题部分写法可能触发 GCC15.1 在 O2 下的编译器 bug。建议 C++ 用户以 C++14（GCC9）提交代码。

题目描述

给定一个 $1 \sim n$ 的排列 $p$，构建其笛卡尔树。

即构建一棵二叉树，满足：

1. 每个节点的编号满足二叉搜索树的性质。
2. 节点 $i$ 的权值为 $p_i$，每个节点的权值满足小根堆的性质。

输入格式

第一行一个整数 $n$。

第二行一个排列 $p_{1 \dots n}$。

输出格式

设 $l_i,r_i$ 分别表示节点 $i$ 的左右儿子的编号（若不存在则为 $0$）。

一行两个整数，分别表示 $\operatorname{xor}_{i = 1}^n i \times (l_i + 1)$ 和 $\operatorname{xor}_{i = 1}^n i \times (r_i + 1)$。

输入样例 #1

5
4 1 3 2 5

输出样例 #1

19 21

说明/提示

【样例解释】

$i$	$l_i$	$r_i$
$1$	$0$
$2$	$1$	$4$
$3$	$0$
$4$	$3$	$5$
$5$	$0$

输入样例 #2

25
21 5 12 10 17 16 15 13 7 2 19 23 22 8 4 25 9 18 3 6 1 11 24 20 14

输出样例 #2

66 631

输入样例 #3

30
26 7 16 14 10 9 12 3 28 8 20 15 29 25 11 5 18 23 24 17 4 13 22 6 21 19 27 30 1 2

输出样例 #3

493 289

【数据范围】

对于 $30\%$ 的数据，$n \le 10^3$。

对于 $60\%$ 的数据，$n \le 10^5$。

对于 $80\%$ 的数据，$n \le 10^6$。

对于 $90\%$ 的数据，$n \le 5 \times 10^6$。

对于 $100\%$ 的数据，$1 \le n \le 10^7$。