Dima's got a staircase that consists of n stairs. The first stair is at height a1, the second one is at a2, the last one is at an (1 ≤ a1 ≤ a2 ≤ ... ≤ an). 

Dima decided to play with the staircase, so he is throwing rectangular boxes at the staircase from above. The i-th box has width wi and height hi. Dima throws each box vertically down on the first wi stairs of the staircase, that is, the box covers stairs with numbers 1, 2, ..., wi. Each thrown box flies vertically down until at least one of the two following events happen:

  * the bottom of the box touches the top of a stair; 
  * the bottom of the box touches the top of a box, thrown earlier. 



We only consider touching of the horizontal sides of stairs and boxes, at that touching with the corners isn't taken into consideration. Specifically, that implies that a box with width wi cannot touch the stair number wi + 1.

You are given the description of the staircase and the sequence in which Dima threw the boxes at it. For each box, determine how high the bottom of the box after landing will be. Consider a box to fall after the previous one lands.

Input

The first line contains integer n (1 ≤ n ≤ 105) — the number of stairs in the staircase. The second line contains a non-decreasing sequence, consisting of n integers, a1, a2, ..., an (1 ≤ ai ≤ 109; ai ≤ ai + 1).

The next line contains integer m (1 ≤ m ≤ 105) — the number of boxes. Each of the following m lines contains a pair of integers wi, hi (1 ≤ wi ≤ n; 1 ≤ hi ≤ 109) — the size of the i-th thrown box.

The numbers in the lines are separated by spaces.

Output

Print m integers — for each box the height, where the bottom of the box will be after landing. Print the answers for the boxes in the order, in which the boxes are given in the input.

Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples

Input

5
1 2 3 6 6
4
1 1
3 1
1 1
4 3


Output

1
3
4
6


Input

3
1 2 3
2
1 1
3 1


Output

1
3


Input

1
1
5
1 2
1 10
1 10
1 10
1 10


Output

1
3
13
23
33

Note

The first sample are shown on the picture.

<image>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// Java program to demonstrate lazy propagation in segment tree
public class LazySegmentTree
{
    final int MAX = 300000;        // Max tree size
    long tree[] = new long[MAX];  // To store segment tree
    long lazy[] = new long[MAX];  // To store pending updates
 
    /*  si -> index of current node in segment tree
        ss and se -> Starting and ending indexes of elements for
                     which current nodes stores sum.
        us and eu -> starting and ending indexes of update query
        ue  -> ending index of update query
        diff -> which we need to add in the range us to ue */
    public static void main(String args[]) throws NumberFormatException, IOException
    {
    	BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    	StringBuilder sb=new StringBuilder();
    	int n=Integer.parseInt(br.readLine());
    	long arr[] = new long[n];
    	StringTokenizer st=new StringTokenizer(br.readLine());
    	for (int i = 0; i < arr.length; i++) {
			arr[i]=Integer.parseInt(st.nextToken());
		}
        LazySegmentTree tree = new LazySegmentTree();
 
        // Build segment tree from given array
        tree.constructST(arr, n);
 
        int m=Integer.parseInt(br.readLine());
        while(m-->0){
        	st=new StringTokenizer(br.readLine());
        	int w=Integer.parseInt(st.nextToken());
        	long h=Long.parseLong(st.nextToken());
        	long max=tree.getSum(n, 0, w-1);
        	tree.updateRange(n, 0, w-1, max+h);
        	sb.append(max).append('\n');
        }
        System.out.print(sb);
        /*
        // Print sum of values in array from index 1 to 3
        System.out.println("Sum of values in given range = " +
                           tree.getSum(n, 1, 3));
 
        // Add 10 to all nodes at indexes from 1 to 5.
        tree.updateRange(n, 1, 5, 10);
 
        // Find sum after the value is updated
        System.out.println("Updated sum of values in given range = " +
                           tree.getSum(n, 1, 3));
                           */
    }
    void updateRangeUtil(int si, int ss, int se, int us,
                         int ue, long value)
    {
        // If lazy value is non-zero for current node of segment
        // tree, then there are some pending updates. So we need
        // to make sure that the pending updates are done before
        // making new updates. Because this value may be used by
        // parent after recursive calls (See last line of this
        // function)
        if (lazy[si] != 0)
        {
            // Make pending updates using value stored in lazy
            // nodes
        	tree[si] = Math.max(tree[si], lazy[si]);
 
            // checking if it is not leaf node because if
            // it is leaf node then we cannot go further
            if (ss != se)
            {
                // We can postpone updating children we don't
                // need their new values now.
                // Since we are not yet updating children of si,
                // we need to set lazy flags for the children
                lazy[si * 2 + 1] = Math.max(lazy[si * 2 + 1], lazy[si]);
                lazy[si * 2 + 2] = Math.max(lazy[si * 2 + 2], lazy[si]);
            }
 
            // Set the lazy value for current node as 0 as it
            // has been updated
            lazy[si] = 0;
        }
 
        // out of range
        if (ss > se || ss > ue || se < us)
            return;
 
        // Current segment is fully in range
        if (ss >= us && se <= ue)
        {
            // Add the difference to current node
            tree[si] = Math.max(tree[si], value);
 
            // same logic for checking leaf node or not
            if (ss != se)
            {
                // This is where we store values in lazy nodes,
                // rather than updating the segment tree itelf
                // Since we don't need these updated values now
                // we postpone updates by storing values in lazy[]
            	lazy[si * 2 + 1] = Math.max(lazy[si * 2 + 1], value);
                lazy[si * 2 + 2] = Math.max(lazy[si * 2 + 2], value);
            }
            return;
        }
 
        // If not completely in rang, but overlaps, recur for
        // children,
        int mid = (ss + se) / 2;
        updateRangeUtil(si * 2 + 1, ss, mid, us, ue, value);
        updateRangeUtil(si * 2 + 2, mid + 1, se, us, ue, value);
 
        // And use the result of children calls to update this
        // node
        tree[si] = Math.max(tree[si * 2 + 1],tree[si * 2 + 2]);
    }
 
    // Function to update a range of values in segment
    // tree
    /*  us and eu -> starting and ending indexes of update query
        ue  -> ending index of update query
        diff -> which we need to add in the range us to ue */
    void updateRange(int n, int us, int ue, long diff)  {
        updateRangeUtil(0, 0, n - 1, us, ue, diff);
    }
 
    /*  A recursive function to get the sum of values in given
        range of the array. The following are parameters for
        this function.
        si --> Index of current node in the segment tree.
               Initially 0 is passed as root is always at'
               index 0
        ss & se  --> Starting and ending indexes of the
                     segment represented by current node,
                     i.e., tree[si]
        qs & qe  --> Starting and ending indexes of query
                     range */
    long getSumUtil(int ss, int se, int qs, int qe, int si)
    {
        // If lazy flag is set for current node of segment tree,
        // then there are some pending updates. So we need to
        // make sure that the pending updates are done before
        // processing the sub sum query
        if (lazy[si] != 0)
        {
            // Make pending updates to this node. Note that this
            // node represents sum of elements in arr[ss..se] and
            // all these elements must be increased by lazy[si]
            tree[si] = Math.max(tree[si], lazy[si]);
 
            // checking if it is not leaf node because if
            // it is leaf node then we cannot go further
            if (ss != se)
            {
                // Since we are not yet updating children os si,
                // we need to set lazy values for the children
                lazy[si * 2 + 1] = Math.max(lazy[si * 2 + 1],lazy[si]);
                lazy[si * 2 + 2] = Math.max(lazy[si * 2 + 2],lazy[si]);
            }
 
            // unset the lazy value for current node as it has
            // been updated
            lazy[si] = 0;
        }
 
        // Out of range
        if (ss > se || ss > qe || se < qs)
            return 0;
 
        // At this point sure, pending lazy updates are done
        // for current node. So we can return value (same as
        // was for query in our previous post)
 
        // If this segment lies in range
        if (ss >= qs && se <= qe)
            return tree[si];
 
        // If a part of this segment overlaps with the given
        // range
        int mid = (ss + se) / 2;
        return Math.max(getSumUtil(ss, mid, qs, qe, 2 * si + 1),
               getSumUtil(mid + 1, se, qs, qe, 2 * si + 2));
    }
 
    // Return sum of elements in range from index qs (query
    // start) to qe (query end).  It mainly uses getSumUtil()
    long getSum(int n, int qs, int qe)
    {
        // Check for erroneous input values
        if (qs < 0 || qe > n - 1 || qs > qe)
        {
            System.out.println("Invalid Input");
            return -1;
        }
 
        return getSumUtil(0, n - 1, qs, qe, 0);
    }
 
    /* A recursive function that constructs Segment Tree for
      array[ss..se]. si is index of current node in segment
      tree st. */
    void constructSTUtil(long arr[], int ss, int se, int si)
    {
        // out of range as ss can never be greater than se
        if (ss > se)
            return;
 
        /* If there is one element in array, store it in
         current node of segment tree and return */
        if (ss == se)
        {
            tree[si] = arr[ss];
            return;
        }
 
        /* If there are more than one elements, then recur
           for left and right subtrees and store the sum
           of values in this node */
        int mid = (ss + se) / 2;
        constructSTUtil(arr, ss, mid, si * 2 + 1);
        constructSTUtil(arr, mid + 1, se, si * 2 + 2);
 
        tree[si] = Math.max(tree[si * 2 + 1],tree[si * 2 + 2]);
    }
 
    /* Function to construct segment tree from given array.
       This function allocates memory for segment tree and
       calls constructSTUtil() to fill the allocated memory */
    void constructST(long arr[], int n)
    {
        // Fill the allocated memory st
        constructSTUtil(arr, 0, n - 1, 0);
    }
}