시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB210574525.862%

문제

Yuto와 Platina가 Non-Decreasing Subarray Game을 하려고 한다. 게임은 길이 N의 배열 A에서 진행된다.

Yuto가 먼저 정수 하나를 부르고, 그걸 듣고 Platina가 정수를 하나 부른다. 이때 얻게 되는 점수는 둘이 부른 수 중 크지 않은 수를 a, 작지 않은 수를 b라고 했을 때, aijb이며 구간 [i, j]가 Non-Decreasing Subarray를 이루는 서로 다른 (i, j) 쌍의 개수이다.

이때 [i, j]가 Non-Decreasing Subarray 를 이룬다는 것은 주어진 배열에서 ixyj이면, Ax Ay라는 것을 뜻한다.

Yuto는 점수가 최소화되기를 원하며, Platina는 점수가 최대화되기를 원한다. 이 게임은 너무나도 재미있어서 부를 수 있는 수의 제한을 바꿔가면서 게임을 T판 진행하려고 한다! 각 판마다 둘이 얻게 될 점수를 구하여라.

입력

첫째 줄에는 두 양의 정수 NT가 주어진다.

둘째 줄에는 배열의 값 A1, A2, A3, ..., AN이 주어진다.

셋째 줄부터 T+2번째 줄까지는 i번째 게임에서 설정한 수의 제한 Li, Ri가 양의 정수로 주어진다. 이는 그 게임에서 두 사람이 부를 수 있는 수가 Li 이상 Ri 이하라는 것을 뜻한다.

출력

각 게임별로 두 사람이 얻게 될 점수를 각 줄에 걸쳐 출력한다.

제한

  • 1 ≤ NT ≤ 500,000
  • 1 ≤ Ai ≤ 109
  • 1 ≤ Li Ri ≤ N

예제 입력 1

8 5
7 10 3 1 9 5 5 2
1 5
2 2
5 8
1 8
3 5

예제 출력 1

4
1
4
7
3
W3sicHJvYmxlbV9pZCI6IjE4OTQ0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiTm9uLURlY3JlYXNpbmcgU3ViYXJyYXkgR2FtZSIsImRlc2NyaXB0aW9uIjoiPHA+WXV0b1x1YzY0MCBQbGF0aW5hXHVhYzAwIE5vbi1EZWNyZWFzaW5nIFN1YmFycmF5IEdhbWVcdWM3NDQgXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVhYzhjXHVjNzg0XHVjNzQwIFx1YWUzOFx1Yzc3NCA8ZW0+TjxcL2VtPlx1Yzc1OCBcdWJjMzBcdWM1ZjQgPGVtPkE8XC9lbT5cdWM1ZDBcdWMxMWMgXHVjOWM0XHVkNTg5XHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5ZdXRvXHVhYzAwIFx1YmEzY1x1YzgwMCBcdWM4MTVcdWMyMTgmbmJzcDtcdWQ1NThcdWIwOThcdWI5N2MgXHViZDgwXHViOTc0XHVhY2UwLCBcdWFkZjhcdWFjNzggXHViNGUzXHVhY2UwIFBsYXRpbmFcdWFjMDAgXHVjODE1XHVjMjE4XHViOTdjIFx1ZDU1OFx1YjA5OCBcdWJkODBcdWI5NzhcdWIyZTQuIFx1Yzc3NFx1YjU0YyBcdWM1YmJcdWFjOGMgXHViNDE4XHViMjk0IFx1YzgxMFx1YzIxOFx1YjI5NCBcdWI0NThcdWM3NzQgXHViZDgwXHViOTc4IFx1YzIxOCBcdWM5MTEgXHVkMDZjXHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWMyMThcdWI5N2MgPGVtPmE8XC9lbT4sIFx1Yzc5MVx1YzljMCBcdWM1NGFcdWM3NDAmbmJzcDtcdWMyMThcdWI5N2MgPGVtPmI8XC9lbT5cdWI3N2NcdWFjZTAgXHVkNTg4XHVjNzQ0IFx1YjU0YywgPGVtPmE8XC9lbT4gJmxlOyA8ZW0+aTxcL2VtPiAmbGU7IDxlbT5qPFwvZW0+ICZsZTsgPGVtPmI8XC9lbT5cdWM3NzRcdWJhNzAgXHVhZDZjXHVhYzA0IFs8ZW0+aTxcL2VtPiwgPGVtPmo8XC9lbT5dXHVhYzAwIE5vbi1EZWNyZWFzaW5nIFN1YmFycmF5XHViOTdjIFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4ICg8ZW0+aTxcL2VtPiwgPGVtPmo8XC9lbT4pIFx1YzMwZFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YjU0YyBbPGVtPmk8XC9lbT4sIDxlbT5qPFwvZW0+XVx1YWMwMCBOb24tRGVjcmVhc2luZyBTdWJhcnJheSBcdWI5N2MgXHVjNzc0XHViOGVjXHViMmU0XHViMjk0IFx1YWM4M1x1Yzc0MCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViYzMwXHVjNWY0XHVjNWQwXHVjMTFjIDxlbT5pPFwvZW0+ICZsZTsgPGVtPng8XC9lbT4gJmxlOyA8ZW0+eTxcL2VtPiAmbGU7IDxlbT5qPFwvZW0+XHVjNzc0XHViYTc0LCA8ZW0+QTxcL2VtPjxzdWI+PGVtPng8XC9lbT4mbmJzcDs8XC9zdWI+JmxlOyA8ZW0+QTxzdWI+eTxcL3N1Yj48XC9lbT5cdWI3N2NcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YjczYlx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+WXV0b1x1YjI5NCBcdWM4MTBcdWMyMThcdWFjMDAgXHVjZDVjXHVjMThjXHVkNjU0XHViNDE4XHVhZTMwXHViOTdjIFx1YzZkMFx1ZDU1OFx1YmE3MCwgUGxhdGluYVx1YjI5NCBcdWM4MTBcdWMyMThcdWFjMDAgXHVjZDVjXHViMzAwXHVkNjU0XHViNDE4XHVhZTMwXHViOTdjIFx1YzZkMFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YWM4Y1x1Yzc4NFx1Yzc0MCBcdWIxMDhcdWJiMzRcdWIwOThcdWIzYzQgXHVjN2FjXHViYmY4XHVjNzg4XHVjNWI0XHVjMTFjIFx1YmQ4MFx1Yjk3YyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzIxOFx1Yzc1OCBcdWM4MWNcdWQ1NWNcdWM3NDQmbmJzcDtcdWJjMTRcdWFmZDRcdWFjMDBcdWJhNzRcdWMxMWMgXHVhYzhjXHVjNzg0XHVjNzQ0IDxlbT5UPFwvZW0+XHVkMzEwIFx1YzljNFx1ZDU4OVx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQhIFx1YWMwMSBcdWQzMTBcdWI5YzhcdWIyZTQgXHViNDU4XHVjNzc0IFx1YzViYlx1YWM4YyBcdWI0MjAgXHVjODEwXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YzVlY1x1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggPGVtPk48XC9lbT5cdWFjZmMgPGVtPlQ8XC9lbT5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmMzMFx1YzVmNFx1Yzc1OCBcdWFjMTIgPGVtPkE8c3ViPjE8XC9zdWI+PFwvZW0+LCA8ZW0+QTxzdWI+MjxcL3N1Yj48XC9lbT4sIDxlbT5BPHN1Yj4zPFwvc3ViPjxcL2VtPiwgLi4uLCA8ZW0+QTxzdWI+TjxcL3N1Yj48XC9lbT5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxNGJcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIDxlbT5UPFwvZW0+KzJcdWJjODhcdWM5ZjggXHVjOTA0XHVhZTRjXHVjOWMwXHViMjk0IDxlbT5pPFwvZW0+XHViYzg4XHVjOWY4IFx1YWM4Y1x1Yzc4NFx1YzVkMFx1YzExYyBcdWMxMjRcdWM4MTVcdWQ1NWMgXHVjMjE4XHVjNzU4Jm5ic3A7XHVjODFjXHVkNTVjIDxlbT5MPFwvZW0+PHN1Yj48ZW0+aTxcL2VtPiwgPFwvc3ViPjxlbT5SPHN1Yj5pPFwvc3ViPjxcL2VtPlx1YWMwMCZuYnNwO1x1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWIyOTQgXHVhZGY4Jm5ic3A7XHVhYzhjXHVjNzg0XHVjNWQwXHVjMTFjIFx1YjQ1MCBcdWMwYWNcdWI3OGNcdWM3NzQgXHViZDgwXHViOTdjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMjE4XHVhYzAwIDxlbT5MPHN1Yj5pPFwvc3ViPjxcL2VtPiZuYnNwO1x1Yzc3NFx1YzBjMSA8ZW0+UjxzdWI+aTxcL3N1Yj48XC9lbT4mbmJzcDtcdWM3NzRcdWQ1NThcdWI3N2NcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YjczYlx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVhYzhjXHVjNzg0XHViY2M0XHViODVjIFx1YjQ1MCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjNWJiXHVhYzhjIFx1YjQyMCBcdWM4MTBcdWMyMThcdWI5N2MgXHVhYzAxIFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4xICZsZTsgPGVtPk48XC9lbT4sJm5ic3A7PGVtPlQ8XC9lbT4mbmJzcDsmbGU7IDUwMCwwMDA8XC9saT5cclxuXHQ8bGk+MSAmbGU7IDxlbT5BPFwvZW0+PHN1Yj48ZW0+aTxcL2VtPiZuYnNwOzxcL3N1Yj4mbGU7IDEwPHN1cD45PFwvc3VwPjxcL2xpPlxyXG5cdDxsaT4xICZsZTsmbmJzcDs8ZW0+TDxcL2VtPjxzdWI+PGVtPmk8XC9lbT4gPFwvc3ViPiZsZTsgPGVtPlI8c3ViPmk8XC9zdWI+PFwvZW0+ICZsZTsmbmJzcDs8ZW0+TjxcL2VtPjxcL2xpPlxyXG48XC91bD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMTg5NDQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJOb24tRGVjcmVhc2luZyBTdWJhcnJheSBHYW1lIiwiZGVzY3JpcHRpb24iOiI8cD5ZdXRvIGFuZCBQbGF0aW5hIGFyZSBnb2luZyB0byBwbGF5IGEgTm9uLURlY3JlYXNpbmcgU3ViYXJyYXkgR2FtZS4gVGhlIGdhbWUgaXMgcGxheWVkIG9uIGFuIGFycmF5ICRBJCBvZiBsZW5ndGggJE4kLjxcL3A+XHJcblxyXG48cD5ZdXRvIGZpcnN0IHNheXMgYW4gaW50ZWdlciwgYW5kIGFmdGVyIHRoYXQsIFBsYXRpbmEgc2F5cyBhbiBpbnRlZ2VyLiBUaGUgbnVtYmVycyBzZWxlY3RlZCBieSB0aGUgcGxheWVycyBzaG91bGQgYmUgaW4gdGhlIGludGVydmFsIGZyb20gJEwkIHRvICRSJCwgaW5jbHVzaXZlLiBMZXQgdGhlIHR3byBzZWxlY3RlZCBpbnRlZ2VycyBiZSAkYSQgYW5kICRiJCwgb3JkZXJlZCBpbiBzdWNoIGEgd2F5IHRoYXQgJGEgXFxsZSBiJC4gVGhlbiB0aGUgc2NvcmUgb2J0YWluZWQgaW4gdGhlIGdhbWUgaXMgdGhlIG51bWJlciBvZiBwYWlycyAkKGksIGopJCBzdWNoIHRoYXQgJGEgXFxsZSBpIFxcbGUgaiBcXGxlIGIkIGFuZCB0aGUgaW50ZXJ2YWwgJFtpLCBqXSQgZm9ybXMgYSBub24tZGVjcmVhc2luZyBzdWJhcnJheSBpbiBhcnJheSAkQSQuPFwvcD5cclxuXHJcbjxwPldlIHNheSB0aGF0ICRbaSwgal0kIGZvcm1zIGEgbm9uLWRlY3JlYXNpbmcgc3ViYXJyYXkgd2hlbiwgZm9yIGVhY2ggJHgkIGFuZCAkeSQgc3VjaCB0aGF0ICRpIFxcbGUgeCBcXGxlIHkgXFxsZSBqJCwgaXQgaXMgdHJ1ZSB0aGF0ICRBW3hdIFxcbGUgQVt5XSQuPFwvcD5cclxuXHJcbjxwPll1dG8gd2FudHMgdGhlIHNjb3JlIHRvIGJlIG1pbmltaXplZCwgYW5kIFBsYXRpbmEgd2FudHMgdGhlIHNjb3JlIHRvIGJlIG1heGltaXplZC4gVGhpcyBnYW1lIGlzIHNvIG11Y2ggZnVuIHRoYXQgd2UgYXJlIGdvaW5nIHRvIHBsYXkgaXQgJFQkIHRpbWVzLiBBbGwgZ2FtZXMgd2lsbCB1c2UgdGhlIHNhbWUgYXJyYXkgJEEkLCBidXQgZGlmZmVyZW50IGdhbWVzIG1pZ2h0IHVzZSBkaWZmZXJlbnQgdmFsdWVzIG9mICRMJCBhbmQgJFIkLjxcL3A+XHJcblxyXG48cD5Bc3N1bWluZyB0aGF0IGJvdGggcGxheWVycyBhcmUgcGxheWluZyBvcHRpbWFsbHksIGZpbmQgdGhlIG51bWJlciBvZiBwb2ludHMgdGhleSB3aWxsIGdldCBpbiBlYWNoIG9mIHRoZSBnYW1lcyBwbGF5ZWQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgJE4kIGFuZCAkVCQgKCQxIFxcbGUgTiwgVCBcXGxlIDUwMFxcLDAwMCQpOiB0aGUgbGVuZ3RoIG9mIHRoZSBhcnJheSBhbmQgdGhlIG51bWJlciBvZiBnYW1lcyBwbGF5ZWQsIHJlc3BlY3RpdmVseS48XC9wPlxyXG5cclxuPHA+SW4gdGhlIHNlY29uZCBsaW5lLCB0aGUgYXJyYXkgdmFsdWVzICRBWzFdJCwgJEFbMl0kLCAkQVszXSQsICRcXGxkb3RzJCwgJEFbTl0kIGFyZSBnaXZlbiAoJDEgXFxsZSBBW2ldIFxcbGUgMTBeOSQpLjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBuZXh0ICRUJCBsaW5lcyBkZXNjcmliZXMgYSBnYW1lIGJ5IHR3byBwb3NpdGl2ZSBpbnRlZ2VycyAkTF9pJCBhbmQgJFJfaSQgKCQxIFxcbGUgTF9pIFxcbGUgUl9pIFxcbGUgTiQpOiB0aGUgdmFsdWVzIG9mICRMJCBhbmQgJFIkIHRvIHVzZSBmb3IgdGhpcyBnYW1lLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGdhbWUsIHByaW50IHRoZSBzY29yZSBpbiB0aGlzIGdhbWUgb24gYSBzZXBhcmF0ZSBsaW5lLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=