题意：给出一个长度为$N$的数列，$Q$次询问，每一次询问$[l,r]$之间的最大子段和，相同的数只计算一次。所有数字的绝对值$\leq 10^5$
GSS系列中不板子的大火题，单独拿出来写
因为相同的数字只计算一次，像GSS1中的合并操作就无法进行，传统做法失效，我们需要一种更强大的做法。
考虑到去重，与HH的项链很相似，所以考虑离线、对询问以$r$从小到大进行排序后进行计算。
考虑到每一次$r$的增加都会产生新的可能的最大子段和，我们用如下方式维护线段树：对于第$i$个叶子节点，它包含两个元素：$sum$表示$\sum \limits_i^r num_i$（不算重复元素），$hisMax$表示$\sum \limits_i^r num_i$在曾经的过程中取到的最大值（也就是左端点为$l$，右端点在$[l,r]$之间的最大子段和）。而对于每一个非叶子节点，它的$sum$和$hisMax$都取其左右儿子的最大值。这样每一次询问操作只需要询问$[l,r]$的$hisMax$即可。
对于$r$的右移操作，设$pre_i$表示数字$i$最后一次出现的位置，将右端点从$r$移到$r+1$的过程就是对$pre_{num_{r+1}}$到$r+1$的所有位置加上$num_{r+1}$的操作。
考虑到复杂度，所以我们需要用到懒标记，而pushdown在其中是十分讲究的，具体代码和解释在下面
（$h\_tag$表示$hisMax$的标记（相当于在当前$hisMax$还需要加多少），$s\_tag$表示$sum$的懒标记）
inline void pushdown(int now){
if(Tree[now].h_tag){
Tree[lch].hisMax = max(Tree[lch].hisMax , Tree[lch].sum + Tree[now].h_tag);
Tree[rch].hisMax = max(Tree[rch].hisMax , Tree[rch].sum + Tree[now].h_tag);
Tree[lch].h_tag = max(Tree[lch].h_tag , Tree[lch].s_tag + Tree[now].h_tag);
Tree[rch].h_tag = max(Tree[rch].h_tag , Tree[rch].s_tag + Tree[now].h_tag);
/*
h_tag和hisMax实质上都是前缀最大值
在一个后缀加入的时候（也就是Tree[now].h_tag传下来的时候），s_tag和sum可以跟当前的h_tag接上变成一个新的前缀而s_tag与h_tag两个标记对应的区间的左端点一定是一致的，sum和hisMax显然是一致的，于是h_tag和hisMax可以这样转移
*/
Tree[now].h_tag = ;
}
if(Tree[now].s_tag){
Tree[lch].sum += Tree[now].s_tag;
Tree[rch].sum += Tree[now].s_tag;
Tree[lch].s_tag += Tree[now].s_tag;
Tree[rch].s_tag += Tree[now].s_tag;
Tree[now].s_tag = ;
}//这个没什么好说的，基本的线段树操作
}
//注意一定要先传h_tag再传s_tag，因为h_tag和hisMax传下来的时候是与之前的那一段进行连接，而不是与当前计算的这一段进行连接完整代码：
#include<bits/stdc++.h>
#define lch (now << 1)
#define rch (now << 1 | 1)
#define mid ((l + r) >> 1)
#define int long long
//This code is written by Itst
using namespace std;
inline int read(){
;
;
char c = getchar();
while(c != EOF && !isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(c != EOF && isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
;
struct node{
int sum , hisMax , s_tag , h_tag;
}Tree[MAXN << ];
struct query{
int l , r , ind;
}now[MAXN];
map < int , int > appear;
int N , Q , num[MAXN] , ans[MAXN];
bool operator <(query a , query b){
return a.r < b.r;
}
inline void pushup(int now){
Tree[now].sum = max(Tree[lch].sum , Tree[rch].sum);
Tree[now].hisMax = max(Tree[lch].hisMax , Tree[rch].hisMax);
}
inline void pushdown(int now){
if(Tree[now].h_tag){
Tree[lch].hisMax = max(Tree[lch].hisMax , Tree[lch].sum + Tree[now].h_tag);
Tree[rch].hisMax = max(Tree[rch].hisMax , Tree[rch].sum + Tree[now].h_tag);
Tree[lch].h_tag = max(Tree[lch].h_tag , Tree[lch].s_tag + Tree[now].h_tag);
Tree[rch].h_tag = max(Tree[rch].h_tag , Tree[rch].s_tag + Tree[now].h_tag);
Tree[now].h_tag = ;
}
if(Tree[now].s_tag){
Tree[lch].sum += Tree[now].s_tag;
Tree[rch].sum += Tree[now].s_tag;
Tree[lch].s_tag += Tree[now].s_tag;
Tree[rch].s_tag += Tree[now].s_tag;
Tree[now].s_tag = ;
}
}
void modify(int now , int l , int r , int L , int R , int add){
if(l >= L && r <= R){
Tree[now].s_tag += add;
Tree[now].sum += add;
Tree[now].hisMax = max(Tree[now].hisMax , Tree[now].sum);
Tree[now].h_tag = max(Tree[now].h_tag , Tree[now].s_tag);
return;
}
pushdown(now);
if(mid >= L)
modify(lch , l , mid , L , R , add);
if(mid < R)
modify(rch , mid + , r , L , R , add);
pushup(now);
}
int query(int now , int l , int r , int L , int R){
if(l >= L && r <= R)
return Tree[now].hisMax;
pushdown(now);
;
if(mid >= L)
maxN = query(lch , l , mid , L , R);
if(mid < R)
maxN = max(maxN , query(rch , mid + , r , L , R));
return maxN;
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1557.in" , "r" , stdin);
//freopen("1557.out" , "w" , stdout);
#endif
N = read();
; i <= N ; ++i)
num[i] = read();
Q = read();
; i <= Q ; ++i){
now[i].l = read();
now[i].r = read();
now[i].ind = i;
}
sort(now + , now + Q + );
; i <= Q ; ++i){
].r + ; j <= now[i].r ; ++j){
modify( , , N , appear[num[j]] + , j , num[j]);
appear[num[j]] = j;
}
ans[now[i].ind] = query( , , N , now[i].l , now[i].r);
}
; i <= Q ; ++i)
printf("%lld\n" , ans[i]);
;
}