Masala #0172

Xotira 64 MB Vaqt 1000 ms
14
Muallif: Sirojiddin

Golomb ketma-ketligi

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.


Kiruvchi ma'lumotlar:

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


Chiquvchi ma'lumotlar:

Bitta butun son – masalaning javobi.


Misollar
# input.txt output.txt
1
5
11
2
12
44
Izoh:

Ketma-ketlikning dastlabki 5 ta hadi: \({\{ 1, 2, 2, 3, 3}\}\). Ularning yig'indisi esa 11.