说明

本题不再额外提供样例文件。

题目描述

一个长度为 N 的括号字符串，仅包含 ( 或 )。

每次你可以选择两个相邻的且匹配的括号删除，即找到一个长度为 2 的子串 () 并删除。每次删除后，剩余字符会靠拢在一起，相对位置不变。

问：最后期望能够剩余多少个括号？

例如：字符串 ((())) 可以不断删除直至为空串；

(()()))( 可以不断删除最后剩余 2 个括号：)(。

输入格式

一个整数 N

输出格式

一个实数，表示答案，要求四舍五入保留 3 位小数。

样例1输入

2

样例1输出

1.500

样例1解释

2 个字符，有 4 种可能：

（1）(( 剩余 2 个括号

（2）() 剩余 0 个括号

（3）)( 剩余 2 个括号

（4）)) 剩余 2 个括号

期望值 = 2×1/4 + 0×1/4 + 2×1/4 + 2×1/4 = 1.500

样例2输入

1983

样例2输出

70.070

数据范围

1 ≤ N ≤ 2000