I. Ivan And Mega Queries
time limit per test
1.2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Ivan learned how to do RMQ queries, so he was introduced to the RMQ mega query. Given a set of distinct indices $$$ind$$$, ordered in increasing order $$$ind_1 \lt ind_2 \lt \dots \lt ind_m$$$. An RMQ mega query with these indices, over the sequence $$$a$$$, is defined as:

$$$$$$\sum_{i=1}^m\sum_{j=i}^m \max{ \left( a_{ind_i},\, \dots, \, a_{ind_j}\right) }$$$$$$

Ivan just learned how to solve them, now he proposes $$$q$$$ mega queries.

Input

the first line receives a single integer $$$n$$$ ($$$1 \le n \le 5\times {10}^5$$$), indicating the size of the sequence $$$a$$$.

The second line contains $$$n$$$ integers $$$a_i$$$ ($$$1 \le a_i \le {10}^9$$$) separated by spaces, representing the sequence $$$a$$$.

The third line receives a single integer $$$q$$$ ($$$1 \le q \le 3\times {10}^5$$$), indicating the number of mega queries.

The following $$$2q$$$ lines contain the mega queries.

The first line of each mega query is an integer $$$m$$$ ($$$1 \le m \le n$$$), the number of indices in the mega query.

The second line of each mega query contains the indices $$$ind$$$, ordered in increasing order.

The sum total of the $$$m$$$ is at most $$$5\times {10}^5$$$.

Output

For each query, print a single line with an integer indicating the answer.

Example
Input
6
2 7 5 8 1 2
5
2
1 6
6
1 2 3 4 5 6
4
1 3 5 6
4
1 3 4 5
4
2 4 5 6
Output
12
136
51
63
60