数列 \(A\) を 考えやすいように書き並べてみましょう。

1 | 2 1 2 | 3 2 1 2 3 | 4 3 2 1 2 3 4 | 5 4 3 2 1 2 3 4 5 | ...

こう見ると、 \(i\) 番目の「ブロック」について以下の性質を得ることになります。

• \(i\) 番目のブロックの大きさは \(2 \times i-1\) である。
• \(i\) 番目のブロックの \(j\) 番目の要素は
  • \(j \le i\) である場合、 \(i-j+1\)
  • そうでない場合、 \(j-i+1\) となります。

さて、ここから \(N\) 番目の要素が何番目のブロックの何番目の要素かを求めることができればこの問題は解けることになります。

\(N\) 番目の要素が何番目のブロックに属するかが分かればその情報からブロック内で何番目かを求めることができるので、前者を求めにかかることを考えます。ここで以下の性質が利用できます。

\(k\) 番目のブロックの末尾は全体で \((1+2 \times k-1) \times k \times \frac{1}{2}\) 番目の要素となります。(等差数列の和の公式より)
この \(k\) に対して二分探索を行えば、 \(N\) が何番目のブロックに属するかが分かります。

実装例(C++):

#include<bits/stdc++.h>

using namespace std;

long long f(long long k){
  return ((1+2*k-1)*k)/2;
}

int main(){
  long long n;
  cin >> n;
  long long st=0,fi=3e9;
  while(st<=fi){
    long long te=(st+fi)/2;
    if(f(te)<n){st=te+1;}
    else{fi=te-1;}
  }
  long long i=st;
  long long j=n-f(st-1);
  if(j<=i){cout << i-j+1 << "\n";}
  else{cout << j-i+1 << "\n";}
  return 0;
}