يعلّم تشوباتي غريغوري ميليخوف كيفية تنفيذ ضربة باكلان باستخدام سيف. كأهداف ، يستخدمون n الأشجار في صف واحد ، مرقمة من 1 إلى n . شوباتي ، قدر قوة جميع الأشجار بالأعداد الطبيعية ، وكتبها. لكل شجرة تمكن ميليخوف من قطعها ، يتلقى عددًا من النقاط يساوي الرقم المكتوب على الشجرة ، وإذا لم يستطع ، فإنه يخسر نفس المقدار.
طلب Chubaty من Grigory ضرب الأشجار من l إلى r ، بترتيب تصاعدي لأرقامها. لقد أصاب ميليخوف كتفه مؤخرًا ، لذا يمكنه أن يقطع شجرة بنجاح كل مرة ، أي إذا قطع شجرة برقم i ، فلن يتمكن من قطع شجرة برقم < code> i + 1 ، ولكن سيتمكن من قطع الشجرة بالرقم i + 2 إلخ.
طلب Chubat m ذات مرة من Grigory أداء الضربات ، لكنه نسي الأشجار التي يمكن أن يقطعها Melekhov. ساعده في تحديد عدد النقاط التي سجلها جريجوري في كل محاولة.
& nbsp؛
إدخال
يحتوي السطر الأول على رقمين n و m ( \ (1 & lt؛ = n، m & lt؛ = 100000 \) )
يحتوي السطر الثاني على أرقام n - قوة كل الأشجار ، حيث يتم كتابة قوة الشجرة i في الموضع i .
تحتوي سطور
m التالية على أزواج من الأرقام
l و
r (
\ (1 & lt ؛ = l & lt؛ = r & lt؛ = n \) ) ، وهذا يعني أي قطعة من الأشجار طلب تشوباتي قطعها.
& nbsp؛
الإخراج
لكل استعلام اطبع عدد النقاط التي حصل عليها Grigory في هذه المحاولة.
نبسب ؛
نبسب ؛
أمثلة
| # |
إدخال |
الإخراج |
<الجسم>
| 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
|