벌목
Problem
<사업부>
Chubaty는 Grigory Melekhov에게 세이버로 Baklan 타격을 수행하는 방법을 가르칩니다. 대상으로 그들은 1에서 n까지 번호가 매겨진 n 트리를 연속으로 사용합니다. Chubaty는 자연수로 모든 나무의 강도를 추정하고 기록했습니다. Melekhov가 자를 수 있는 각 나무에 대해 나무에 적힌 숫자와 같은 수의 점수를 받고, 자를 수 없으면 같은 양의 점수를 잃습니다.
Chubaty는 Grigory에게 l에서 r까지 트리를 숫자의 오름차순으로 치라고 요청합니다. Melekhov는 최근에 어깨를 다쳤기 때문에 매번 성공적으로 나무를자를 수 있습니다. 즉, i 번호의 나무를 자르면 < code>i + 1, 그러나 숫자가 i + 2 등인 트리를 잘라낼 수 있습니다.
Chubat
m은 한때 Grigory에게 타격을 가하라고 요청했지만 Melekhov가 어떤 나무를 벨 수 있는지 잊어 버렸습니다. 각 시도에 대해 Gregory가 득점한 점수를 확인하도록 도와주세요.
입력
첫 번째 줄에는 2개의 숫자 n 및 m이 포함됩니다(\(1 <= n, m <= 100000 \))
두 번째 줄에는 n개의 숫자가 포함되어 있습니다. 모든 트리의 강도입니다. 여기서 트리 i의 강도는 위치 i에 기록됩니다.
다음 m 줄에는 숫자 l 및 r 쌍이 포함됩니다(\(1 < ; = l <= r <= n\)), Chubaty가 잘라달라고 요청한 나무 조각을 의미합니다.
출력
각 쿼리에 대해 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
|