对于一组点（其 $x$ 坐标两两不同且 $y$ 坐标两两不同），构建笛卡尔树（Cartesian Tree）的方法是唯一的。一个男孩将 $n$ 个点随机撒入一个 $1 \times 1$ 的正方形中，并依次将它们插入到一棵笛卡尔树中（该树初始为空）。如果新插入的节点在插入后的新树中不是叶子节点，我们就称发生了一次“重构”（rebuilding）。你需要计算发生重构的期望次数。

由于任意两个点具有相同 $x$ 坐标或相同 $y$ 坐标的概率为零，我们可以假设所有点的坐标都是两两不同的。

输入格式

输入仅包含一行，一个整数 $n$（$1 \le n \le 10^9$）。

输出格式

输出该问题的答案，与标准答案的绝对误差或相对误差不超过 $10^{-9}$。

样例

输入 1

2

输出 1

0.5000000000

输入 2

5

输出 2

2.2388888888

说明

笛卡尔树是一种结合了二叉搜索树和二叉堆的数据结构。

严格来说，笛卡尔树是一棵二叉树，其中每个节点存储一个二元组 $(x, y)$，其中 $x$ 为键值（key），$y$ 为优先级（priority）。笛卡尔树关于 $x$ 必须满足二叉搜索树的性质，关于 $y$ 必须满足二叉堆的性质。如果我们假设所有的 $x$ 和 $y$ 都是两两不同的，那么对于一个元素 $(x_0, y_0)$，其所有左子树中的后代都满足 $x < x_0$，所有右子树中的后代都满足 $x > x_0$，且其所有后代都必须满足 $y < y_0$。（定义翻译自 ITMO Wikipages）。