+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- یک دنباله از اعداد صحیح مثل $a_1, a_2, \dots, a_n\,$ داریم. $q$ درخواست داده می‌شود. دو نوع درخواست داریم. در هر درخواست دو عدد صحیح $l$ و $r$ که $1 \leq l \leq r \leq n$ است داده می‌شود از شما می‌خواهیم همه‌ی اعداد $a_l, a_{l+1}, \dots, a_r\,$ را به $f(a_l), f(a_{l+1}), \dots, f(a_r)\,$ تغییر داده و در جایگاه آن بنویسید، و سپس مجموع اعداد همین زیربازه $l$ تا $r$ را بعد از تغییر چاپ کنید. یعنی در هر درخواست یک بازه پشت سر هم از دنباله تغییر می‌کند و هر عدد دنباله تبدیل به $f$ خود می‌شود. مقدار $f(k)$ از رابطه‌ی زیر بدست می‌آید: $$f(k) = \lfloor \sqrt{k} \rfloor . (\lfloor \sqrt{k} \rfloor - 1)$$ # ورودی در سطر اول ورودی، عدد صحیح و مثبت $n$ آمده که تعداد اعضای دنباله‌ی را نشان می‌دهد. $$1 \leq n \leq 100 \, 000$$ در سطر دوم ورودی، $n$ عدد صحیح که با یک فاصله از هم جدا شده‌اند آمده است. عدد $i$ ام ظاهر شده مقدار $a_i$ را نشان می‌دهد. $$1 \leq a_i \leq 1000 \, 000$$ در سطر سوم ورودی، عدد صحیح $q$ آمده که تعداد درخواست‌ها را نشان می‌دهد. $$1 \leq q \leq 1000 \, 000$$ در $q$ سطر بعدی، در هر سطر یک درخواست می‌آید. هر درخواست به صورت دو عدد $l$ و $r$ نشان داده می‌شود که $l$ و $r$ به ترتیب شروع و پایان بازه‌ی درخواست را نشان می‌دهند. $$1 \leq l \leq r \leq n$$ # خروجی به تعداد درخواست‌ها، مقدار مجموع زیربازه را بعد از تغییر گفته شده چاپ کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 5 10 4 11 3 7 3 2 4 1 3 1 5 ```` ## خروجی نمونه ۱ ``` 8 8 4 ````

حل سؤال در بانک سؤالات