笛卡尔树【模板】

题目描述

给定一个1∼n的排列p，构建其笛卡尔树。
即构建一棵二叉树，满足：
每个节点的编号满足二叉搜索树的性质。
节点i的权值为，每个节点的权值满足小根堆的性质。

输入

第一行一个整数n。 第二行一个排列p1,p2,...,pn。

输出

设li,ri,分别表示节点i的左右儿子的编号（若不存在则为0）。 一行两个整数，分别表示i×(li+1)的异或和、i×(ri+1)的异或和。

样例

提示

对于100% 的数据，1≤n≤10^7。