You are given the following:

• An array $A$ of length n that contains integers
• $DP$ of length $n$ 
• Arrays $L$ and $R$ of length $n$ that contain integers

You are also provided with the following attributes:

• If $i=1$, then $L_i=R_i=1$

• If $2\leq i\leq n$, then $1\leq L_i\leq R_i\lt i$

• $DP_1=A_1$

• $DP_i=min(DP[L_i,R_i])+A_i$

The element $A[x,y]$ is defined to be all the elements that are available in $[a,b]$ of array $A$. For example, $DP[2,3]$ indicates $DP_2$ and $DP_3$.

You are also provided with $q$ queries that state the following:

• You are given two integers $x$ and $y$.
• You are required to replace $DP[1,x]$ to $y$ and then update the remaining part of $DP$. Now, print $DP_n$.

Note

• You must repeat this task every time you are given these two integers.
• The queries are independent of each other. Therefore, the current query cannot modify the next query.