题目描述

给定⼀个 $1\sim n$ 的排列 $P$，即长度为 $n$，且 $1\sim n$ 中所有数字都恰好出现一次的序列。现在按顺序将排列中的元素一一插入到初始为空的二叉搜索树中（左小右大），问最后每个节点的父亲节点的元素是什么。特别地，根节点的父亲节点元素视为 $0$。

输入描述

第一行一个整数 $n (1\leq n\leq 10^5)$，表示排列 P 中的元素个数。