\(0\)-indexed，半開区間で考える． 操作を一つの単位として，ブロック毎に考える． 数列の値も \(1\) 引いて考える．
- \(i\)番目のブロックは \(i, i-1, i-2, \cdots , 0, 1, 2, \cdots, i-1, i\) の \(2i+1\) 個．
- \(i\) ブロックの \(x\) 番目は \(\vert i-x \vert\)
あとは， \(N\) に対して \(i,x\) を求めればよい． \([0,i)\) 番目のブロックに含まれるのは \(i^{2}\) 個． \(i\) は \(N^{1/2}\) 程度になるので，その周辺を 探索すれば十分． そのとき， \(i \geq 0\) であることに注意．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, m, k, q;
cin >> n;
--n;
ll i = -1;
ll s = sqrt(n);
srep(k, max(0ll,s-5),s+5){ // rem: k >= 0
if(in(n, square(k), square(k+1))){
i = k;
break;
}
}
assert(i >= 0);
ll x = n - square(i);
cout << abs(i-x)+1 << endl;
return 0;
}
