Problem
Chubaty, Grigory Melekhov'a kılıçla Baklan saldırısı yapmayı öğretir. Hedef olarak, 1 ile n arasında numaralandırılmış n ağaçlarını arka arkaya kullanırlar. Chubaty, tüm ağaçların gücünü doğal sayılarla tahmin etti ve bunları yazdı. Melekhov'un kesebildiği her ağaç için ağaçta yazan sayı kadar puan alır ve kesemezse aynı miktarı kaybeder.
Chubaty, Grigory'den l'den r'e kadar olan ağaçları sayılarının artan sırasına göre vurmasını ister. Melekhov kısa bir süre önce omzunu incitti, böylece her seferinde bir ağacı başarılı bir şekilde kesebilir, yani i numaralı bir ağacı keserse, i numaralı bir ağacı kesemez. code>i + 1, ancak i + 2 vb. numaralı ağacı kesebilecek.
Chubat
m bir keresinde Grigory'den darbeler yapmasını istedi, ancak Melekhov'un hangi ağaçları kesebileceğini unuttu. Gregory'nin her denemede kaç puan kazandığını belirlemesine yardım edin.
Giriş
İlk satır 2 sayı içerir n ve m (\(1 <= n, m <= 100000) \))
İkinci satır, n sayılarını içerir - tüm ağaçların gücü, burada i ağacının gücü i konumunda yazılır.
Aşağıdaki m satırları l ve r sayı çiftlerini içerir (\(1 < ; = l <= r <= n\)), Chubaty'nin hangi ağaç parçasını kesmesini istediği anlamına gelir.
Çıktı
Her sorgu için Grigory'nin bu denemede kaç puan kazandığını yazdırın.
Örnekler
| # |
Girdi |
Çıktı |
| 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
|