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.