{"raw_statement":[{"iden":"problem statement","content":"For integers $l, r$, let $[l, r]$ denote the set of all integers from $l$ through $r$. That is, $[l, r] = \\lbrace l, l+1, l+2, \\ldots, r-1, r\\rbrace$.\nYou are given $N$ pairs of integers $(L_1, R_1), (L_2, R_2), \\ldots, (L_N, R_N)$. Based on these pairs, consider an undirected graph $G$ defined as follows:\n\n*   It has $N$ vertices numbered $1, 2, \\ldots, N$.\n*   For all $i, j \\in [1, N]$, there is an undirected edge between vertices $i$ and $j$ if and only if the intersection of $[L_i, R_i]$ and $[L_j, R_j]$ is empty.\n\nIn addition, for each $i = 1, 2, \\ldots, N$, define the weight of vertex $i$ to be $W_i$.\nYou are given $Q$ queries about $G$. Process these queries in the order they are given. For each $i = 1, 2, \\ldots, Q$, the $i$\\-th query is the following:\n\n> You are given integers $s_i$ and $t_i$ (both between $1$ and $N$, inclusive) such that $s_i \\neq t_i$. Determine whether there exists a path from vertex $s_i$ to vertex $t_i$ in $G$. If it exists, print the minimum possible **weight** of such a path.\n\nHere, the weight of a path from vertex $s$ to vertex $t$ is defined as the sum of the weights of the vertices on that path (including both endpoints $s$ and $t$)."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq Q \\leq 2 \\times 10^5$\n*   $1 \\leq W_i \\leq 10^9$\n*   $1 \\leq L_i \\leq R_i \\leq 2N$\n*   $1 \\leq s_i, t_i \\leq N$\n*   $s_i \\neq t_i$\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$W_1$ $W_2$ $\\cdots$ $W_N$\n$L_1$ $R_1$\n$L_2$ $R_2$\n$\\vdots$\n$L_N$ $R_N$\n$Q$\n$s_1$ $t_1$\n$s_2$ $t_2$\n$\\vdots$\n$s_Q$ $t_Q$"},{"iden":"sample input 1","content":"5\n5 1 4 2 2\n2 4\n1 2\n7 8\n4 5\n2 7\n3\n1 4\n4 3\n5 2"},{"iden":"sample output 1","content":"11\n6\n-1\n\n$G$ is a graph with four undirected edges: $\\lbrace 1, 3\\rbrace, \\lbrace 2, 3\\rbrace, \\lbrace 2, 4\\rbrace, \\lbrace 3, 4\\rbrace$.\n\n*   For the first query, there is a path from vertex $1$ to vertex $4$ given by $1 \\to 3 \\to 4$. The weight of this path is $W_1 + W_3 + W_4 = 5 + 4 + 2 = 11$, and this is the minimum possible.\n*   For the second query, there is a path from vertex $4$ to vertex $3$ given by $4 \\to 3$. The weight of this path is $W_4 + W_3 = 2 + 4 = 6$, and this is the minimum possible.\n*   For the third query, there is no path from vertex $5$ to vertex $2$. Hence, print `-1`."},{"iden":"sample input 2","content":"8\n44 75 49 4 78 79 12 32\n5 13\n10 16\n6 8\n6 15\n12 15\n5 7\n1 15\n1 2\n5\n5 6\n3 2\n7 5\n4 5\n5 4"},{"iden":"sample output 2","content":"157\n124\n-1\n114\n114"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}