Qızıl açar və ya Buratinin macəraları

Buratino son zamanlar seqment ağacı adlı bir məlumat strukturunu kəşf edib.

Seqment ağacı mahiyyətcə ikili ağacdır, burada hər bir qovşaq [l; r] sərhədləri ilə müəyyən olunan seqment haqqında məlumat saxlayır. Kök qovşaq bütöv ardıcıllığı $[1;N]$ nümayiş etdirir, burada $N$ ardıcıllığın uzunluğudur. Digər bütün qovşaqlarda isə belədir: əgər l = r-dirsə, qovşaq yarpaqd ır. Əks halda, o, dəqiq iki övlad qovşağa malikdir, hansılar ki, müvafiq olaraq $[l;m]$ və [m+1, r] seqmentləri haqqında məlumat saxlayır. Seqment ağacı ən səmərəli şəkildə seqmentlər $[l;m]$ və [m+1, r] bərabər uzunluqda olduqda qurulur. Lakin əgər [l; r] seqmentinin uzunluğu təkdirsə, onda onu bərabər hissələrə bölmək mümkün deyil. Bu zaman ya sol, ya da sağ seqment digərində bir vahid uzun olacaq. Hər performansdan sonra Buratino uzunluğu $N$ olan massiv üçün seqment ağacı qurur. Hər dəfə isə, bərabər bölmə mümkün olmadıqda, təsadüfi olaraq, solunmu, yoxsa sağınmı daha uzun olacağına qərar verir.

Sənin vəzifən müəyyən etməkdir: Buratino neçə müxtəlif seqment ağacı qura bilər.