قطع درختان
Problem
چوباتی به گریگوری ملخوف می آموزد که چگونه یک ضربه باکلان را با سابر انجام دهد. به عنوان هدف، از درخت‌های n در یک ردیف استفاده می‌کنند که از 1 تا n شماره‌گذاری شده‌اند. چوباتی، قدرت همه درختان را با اعداد طبیعی تخمین زد و آنها را یادداشت کرد. به ازای هر درختی که ملخوف توانسته است آن را قطع کند، تعدادی امتیاز برابر با تعداد نوشته شده روی درخت دریافت می کند و اگر نتوانست، همان مقدار را از دست می دهد.
چوباتی از گریگوری می‌خواهد تا درختان را از l تا r به ترتیب صعودی تعداد آنها بزند. ملخوف اخیراً شانه‌اش آسیب دیده است، بنابراین می‌تواند یک بار در میان با موفقیت یک درخت را قطع کند، یعنی اگر درختی را با شماره i قطع کند، دیگر نمی‌تواند درختی را با شماره < قطع کند. code>i + 1، اما می تواند درخت را با شماره i + 2 و غیره قطع کند.
چوبات
m یک بار از گریگوری خواست ضرباتی بزند، اما او فراموش کرد که ملخوف چه درختانی را می تواند قطع کند. به او کمک کنید تعیین کند که گرگوری برای هر تلاش چند امتیاز کسب کرده است.
ورودی
خط اول شامل 2 عدد n و m است (\(1 <= n، m <= 100000 \))
خط دوم شامل اعداد n است - قدرت همه درختان، که در آن قدرت درخت i در موقعیت i نوشته شده است.
خطوط m زیر شامل جفت اعداد l و r (\(1 < ; = l <= r <= n\))، به این معنی که چوباتی درخواست قطع کردن کدام تکه درخت را داشت.
خروجی
برای هر پرس و جو، تعداد امتیازهای گریگوری در این تلاش را چاپ کنید.
نمونه‌ها
<سر>
| # |
ورودی |
خروجی |
<بدن>
| 1 |
6 6
1 2 3 4 5 6
16
1 5
2 6
2 5
2 4
2 2
|
-3
3
4
-2
3
2
|