1890. 五边形数(hard version)

将无限多个点按照下图方式摆放,形成无限多个正五边形(下图仅展示四个):

定义第 i 个五边形数是图中第 i 小的五边形边上和内部所包含的点数(特别规定最小的五边形是一个点)。例如,图中,前四个五边形数分别是 1,5,12,22。以第三个五边形为例,它包含的点是红色、黄色和绿色的点,统计得共 12 个。

给定 n,输出第 n 个五边形数是多少。

输入

输入一行一个整数 n(1\le n\le3\times10^9)

输出

输出一行一个整数,代表答案。

样例

标准输入 复制文本
1
标准输出 复制文本
1
标准输入 复制文本
3
标准输出 复制文本
12
标准输入 复制文本
191981000
标准输出 复制文本
55285056445509500
登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 158
通过 46