E - Strange Sequence Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 7 点

問題文

以下の操作によって構成される数列 A の第 N 項を求めてください。

  • 最初、数列 A は空である。
  • 1 以上 10^{100} 以下の全ての整数 i について、以下の操作を i の小さい方から行う。
    • もし i \ge 2 なら、 i,i-1,\dots,2 を数列の末尾にこの順に追加する。
    • その後、 1,2,\dots,i を数列の末尾にこの順に追加する。

制約

  • N は整数
  • 1 \le N \le 10^{18}

入力

入力は以下の形式で標準入力から与えられる。

N

出力

答えを整数として出力せよ。

入力例 1

10

出力例 1

4

A=(1,2,1,2,3,2,1,2,3,4,3,2,1,2,3,4,\dots) なので、第 10 項は 4 です。

入力例 2

1

出力例 2

1

入力例 3

123456789012345678

出力例 3

268452372

入力が 32bit 整数に収まらない場合もあります。

Score : 7 points

Problem Statement

Find the N-th term of the sequence A constructed as follows.

  • Initially, A is empty.
  • For every integer i from 1 through 10^{100} in ascending order, do the following.
    • If i \ge 2, append i,i-1,\dots,2 in this order to the end of A.
    • Then, append 1,2,\dots,i in this order to the end of A.

Constraints

  • N is an integer.
  • 1 \le N \le 10^{18}

Input

Input is given from Standard Input in the following format:

N

Output

Print the answer as an integer.

Sample Input 1

10

Sample Output 1

4

We have A=(1,2,1,2,3,2,1,2,3,4,3,2,1,2,3,4,\dots), where the 10-th term is 4.

Sample Input 2

1

Sample Output 2

1

Sample Input 3

123456789012345678

Sample Output 3

268452372

Input may not fit into a 32-bit integer.