测试数据来自 nnu_contest/1235

E.奇怪的程序(Medium)

时间限制：3秒
空间限制：512MB

题目背景

本题的Medium版本与Easy版本唯一的区别在于，该版本\(n,m\le10^6\)

你得到了一份奇怪的代码。

根据说明文档，这份代码只由两种字符构成。程序开始时将自动定义一个初值为0的整型变量X。两个字符和相对应的作用是：

'+'，将X增加1。

'-'，将X减少1。

题目描述

现有m个询问，每个询问给出两个正整数\(l\le r\)

问：仅保留程序的第[l,r]个字符，程序在运行过程中，变量X会取到多少种不同的取值？

初始化的赋值不计算在内。

输入格式

第一行包括两个整数\(n,m\)，分别表示程序的长度和询问的个数。

第二行包括一个长度为\(n\)的字符串，字符串中仅包含提到的两种字符。

之后的\(m\)行每行包含两个正整数\(1\le l\le r\le n\)

输出格式

共\(m\)行，每行一个整数表示答案。

数据范围及限制

\(n,m\le 10^6\)

样例输入

8 4
-+--+--+
1 8
2 8
2 5
1 1

样例输出

4
4
3
1

样例解释

对于第一次询问，
若执行1~8个字符对应的代码，则x的值分别为:-1,0,-1,-2,-1,-2,-3,-2。一共有四个不同的值。
对于第三次询问，x的值分别为1,0,-1,0,一共有三个不同的值。
对于最后一次询问，x的值为:1，一共有一个不同的值。