B"You are given a tree of n vertices and n - 1 edges. The i -th vertex has an initial weight a_i . Let the distance d_v(u) from vertex v to vertex u be the number of edges on the path from v to u . Note that d_v(u) = d_u(v) and d_v(v) = 0 . Let the weighted distance w_v(u) from v to u be w_v(u) = d_v(u) + a_u . Note that w_v(v) = a_v and w_v(u) neq w_u(v) if a_u neq a_v . Analogically to usual distance, let's define the eccentricity e(v) of vertex v as the greatest weighted distance from v to any other vertex (including v itself), or e(v) = max limits_{1 <= u <= n}{w_v(u)} . Finally, let's define the radius r of the tree as the minimum eccentricity of any vertex, or r = min limits_{1 <= v <= n}{e(v)} . You need to perform m queries of the following form: After performing each query, print the radius r of the current tree. The first line contains the single integer n ( 2 <= n <= 2 cdot 10^5 ) -- the number of vertices in the tree. The second line contains n integers a_1, ... , a_n ( 0 <= a_i <= 10^6 ) -- the initial weights of vertices. Next n - 1 lines contain edges of tree. The i -th line contains two integers u_i and v_i ( 1 <= u_i, v_i <= n ; u_i neq v_i ) -- the corresponding edge. The given edges form a tree. The next line contains the single integer m ( 1 <= m <= 10^5 ) -- the number of queries. Next m lines contain queries -- one query per line. The j -th query contains two integers v_j and x_j ( 1 <= v_j <= n ; 0 <= x_j <= 10^6 ) -- a vertex and it's new weight. Print m integers -- the radius r of the tree after performing each query. After the first query, you have the following tree: The tree after the second query: After the third query, the radiu"...