Masala #0172

Golomb ketma-ketligi \(G_1, G_2, \space \dots \space, G_n\) – \(i\) - elementi i soni ketma-ketlikda necha marta uchragani soniga teng bo’lgan o'suvchi ketma-ketlikdir. Ketma-ketlikning bir nechta dastlabki qiymatlari:
\([1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, \space \dots]\).

Misol uchun, \(G_1 = 1\), sababi 1 soni ketma-ketlikda bir marta uchragan. Xuddi shu kabi \(G_4 = 3\), chunki 4 soni ketma-ketlikda 3 marta uchragan.

Golomb ketma-ketligini quyidagi formula orqali topish mumkin:

\(G_1 = 1\)
\(G_{i+1} = 1 +G_{i+1-G_{G_i}} \space\space i \ge1\)

Sizning vazifangiz Golomb ketma-ketligini dastlabki \(n\) ta hadi yig’indisini \((G_1 + G_2 + \dots + G_n)\) topishdan iborat.

Bitta butun \(n\) soni \(( 1 \le n \le 10^9)\).

Bitta butun son – masalaning javobi.