最大去重子段和

题目描述

Y 同学不仅在算法竞赛中表现出色，还是一个追求完美的“去重主义者”。他面前有一个长度为 $N$ 的整数序列 $A = \{a_1, a_2, \ldots, a_N\}$。

Y 同学定义一个连续子段 $[i, j]$（$1 \le i \le j \le N$）的去重和为：该子段中所有不同（Distinct）数值之和。也就是说，如果某个数值在子段中出现了多次，在计算和时只计算一次。 形式化地，令 $S(i, j)$ 表示子段 $A[i \dots j]$ 中出现的不同数值的集合，则该子段的去重和 $V(i, j)$ 定义为：

特别地，允许选取空子段，其去重和为 $0$。

现在，Y 同学需要处理 $Q$ 次询问。每次询问给定两个整数 $x$和 $y$（$1 \le x \le y \le N$），请你找出区间 $[x, y]$ 内的一个子段 $[i, j]$（满足 $x \le i \le j \le y$），使得该子段的去重和 $V(i, j)$ 最大。如果区间内所有非空子段的去重和均为负数，则最大值为 $0$。

请你帮助 Y 同学计算出每次询问的答案。

输入格式

第一行包含一个整数 $N$，表示序列的长度。 第二行包含 $N$ 个整数，表示序列 $A = \{a_1, a_2, \ldots, a_N\}$。 第三行包含一个整数 $Q$，表示询问的次数。 接下来 $Q$ 行，每行包含两个整数 $x$ 和 $y$，表示一次询问的区间范围。

输出格式

对于每次询问，输出一行一个整数，表示在给定区间 $[x, y]$ 内能获得的最大去重子段和。

样例

样例输入 #1

9
4 -2 -2 3 -1 -4 2 2 -6
3
1 2
1 5
4 9

样例输出 #1

4
5
3

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1 \le N \le 100,000$
• $1 \le Q \le 100,000$
• $-100,000 \le a_i \le 100,000$
• $1 \le x \le y \le N$