题目描述

假如有一棵深度为 $n$ 的二叉排序树，而且它只可能有右节点，那最少要旋转多少次才能使它平衡？请输出最少的旋转次数。

输入格式

输入只有 1 行，只有 1 个正整数，表示 $n$。

输出格式

输出只有 1 行，只有 1 个正整数，表示最少要旋转的次数。

5

2

28

30

1327

4054

提示

提示

1. 旋转的知识：https://www.luogu.org/paste/dt2d8zun。
2. 平衡的定义：以任意一个树中节点为根的子树中，根的左右子树的深度差的绝对值不超过 1。

样例 1 解释

样例所对应的原来的二叉树和旋转后的二叉树如下：

数据范围

对于 $100\%$ 的数据，$1 \leq n \leq 2 \times 10^3$。

题目来源

「JYLOI Round 1」 C

Idea：LiuXiangle

Solution：LiuXiangle

Data：LiuXiangle