配点 : 200点

問題文

正整数列 X=(X1,X2,,XX)X = (X_1, X_2, \ldots, X_{|X|}) に対して、

  • f(X):=(全ての隣合うペアの和からなる集合の要素数)f(X) := (全ての隣合うペアの和からなる集合の要素数)
    すなわち、f(X):={Xi+Xi+1:1iX1}f(X) : = |\{ X_i + X_{i + 1} : 1≦i≦|X|-1 \}| と定めます。

(1,2,,N)(1, 2, \ldots, N)の順列 PP を用いて f(P)f(P) と表される値のうち、最小のものを求めてください。

制約

  • 2N10122≦N≦10^{12}
  • 入力はすべて整数

入力

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

NN

出力

答えを出力してください。


入出力例1

入力
3
出力
2

P=(1,2,3)P=(1, 2, 3) とすると、集合は (3,5)(3, 5) となり、要素数は 22 つです。


入出力例2

入力
4
出力
2

P=(4,1,2,3)P=(4, 1, 2, 3) とすると、集合は (5,3,5)(5, 3, 5) となり、要素数は 22 つです。

Submit


Go (1.21)