• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

یک دنباله از اعداد صحیح مثل \(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