Distinct Subarray Query

You are given a sequence s of length \(n\). You have \(q\) queries. Each query is given by six integers \(a\), \(b\), \(c\), \(d\), \(e\), and \(f\).

For each query, for every integer \(L\) such that \(a \le L \le b\), define

[ F(L,r)=\text{the number of distinct numbers in the subarray } s[L \ldots r] \quad (L\le r), ]

and let

[ G(x_1,x_2,\cdots,x_k) = \text{the number of distinct values in } {x_1,x_2,\ldots,x_k}. ]

For each such \(L\), consider the sequence

[ F(L,c),F(L,c+1),\ldots,F(L,d). ]

Because \(F(L,r)\) is non‐decreasing (and increases by exactly \(0\) or \(1\) at each step) the set of distinct numbers in this sequence is exactly the contiguous range from \(F(L,c)\) to \(F(L,d)\). In other words,

[ G(F(L,c),F(L,c+1),\cdots,F(L,d)) = F(L,d)-F(L,c)+1. ]

Your task is to compute the following sum for each query:

[ \sum_{L=a}^{b} \Bigl[ e \le F(L,d)-F(L,c)+1 \le f \Bigr], ]

where \([P]\) is the indicator function which equals \(1\) when the predicate \(P\) is true and \(0\) otherwise.

Note: It is guaranteed that the query parameters always satisfy \(1 \le a \le b \le c \le d \le n\) so that the subarrays are valid.

inputFormat

The first line contains an integer \(n\) \( (1 \le n)\) denoting the length of the sequence.

The second line contains \(n\) integers, representing the sequence \(s\).

The third line contains an integer \(q\) \( (1 \le q)\), the number of queries.

Each of the next \(q\) lines contains six integers \(a\), \(b\), \(c\), \(d\), \(e\), and \(f\) separated by spaces.

outputFormat

For each query, output a single integer representing the sum defined in the problem on a new line.

sample

5
1 2 1 3 2
2
1 2 3 5 1 2
1 2 2 4 2 3

2
2