前缀和前缀最大值
题号：NC274867
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

假定有一个长度为 len 序列 a。

序列 a 的前缀和定义为 s_i=\sum_{j=1}^{i}a_j，1\le i\le len，特别的，定义 s_0=0。

序列 a 的前缀和前缀最大值为 maxx_i=\max_{j=0}^{i}s_j，0\le i\le len。

序列 a 的 A 类价值为 maxx_i 中不同的元素数量。

序列 a 的 B 类价值为所有 a 的所有排列中 A 类价值的种类数。

现在有一个长度为 n 的序列 b。

给出 q 个询问，每个询问包含两个整数 l,r，求序列 b[l::r] 的 B 类价值。

b[l::r] 表示 b[l],b[l+1],...,b[r]。

输入描述:

第一行输入一个整数 n(1\le n\le 10^5)，表示序列 b 的长度。

第二行输入 n 个整数 b_i(1\le |b_i|\le 100)。

接着输入一个整数 q(1\le q\le 10^5)，表示询问次数。

然后 q 行，每行两个整数 l,r(1\le l\le r \le n )。

输出描述:

对于每一个询问，输出一个正整数，表示答案。
示例1

输入

复制 
5
2 3 -1 -2 4
1
2 4

输出

复制 
2

说明

对于第一个询问，序列为 [3,-1,-2]。

有以下 6 种排列。

对于 [3,-1,-2]，S=[0,3,2,0],maxx=[0,3,3,3]，maxx 中有 2 种不同的元素，所以它的 A 类价值为 2。

对于 [3,-2,-1]，S=[0,3,1,0],maxx=[0,3,3,3]，maxx 中有 2 种不同的元素，所以它的 A 类价值为 2。

对于 [-1,3,-2]，S=[0,-1,2,0],maxx=[0,0,2,2]，maxx 中有 2 种不同的元素，所以它的 A 类价值为 2。

对于 [-1,-2,3]，S=[0,-1,-3,0],maxx=[0,0,0,0]，maxx 中有 1 种不同的元素，所以它的 A 类价值为 1。

对于 [-2,-1,3]，S=[0,-2,-3,0],maxx=[0,0,0,0]，maxx 中有 1 种不同的元素，所以它的 A 类价值为 1。

对于 [-2,3,-1]，S=[0,-2,1,0],maxx=[0,0,1,1]，maxx 中有 2 种不同的元素，所以它的 A 类价值为 2。

所以这个询问的序列的所有排列的 A 类价值有 2 种，分别是 1 和 2，也就是这个序列的 B 类价值为 2。
示例2

输入

复制 
10
1 2 5 -5 6 3 -1 6 3 -1
10
1 5
1 3
2 5
3 6
1 10
2 6
6 8
1 7
1 1
2 3

输出

复制 
3
1
2
2
4
3
1
4
1
1