Nam và Nữ là đôi bạn thời thơ ấu, tình cảm dần dần biến thành mối tình tuổi trẻ. Vào ngày sinh nhật của Nữ, Nam quyết định tỏ tình. Nữ đưa ra một thử thách:

Trên một màn hình TV khổng lồ có ~N~ số nguyên dương. Có hai chiếc máy đặc biệt:

• Máy ~1~: ngẫu nhiên xuất ra 0 hoặc 1.
• Máy ~2~: xuất ra một số nguyên dương bất kỳ.

Quy tắc tính điểm cho mỗi lượt:

• Nếu máy ~1~ xuất ra 0: đây là lượt của Nữ. Nữ nhận số điểm bằng với số lượng các số trên màn hình ≤ giá trị mà máy ~2~ đưa ra.
• Nếu máy ~1~ xuất ra 1: đây là lượt của Nam. Nam nhận số điểm bằng với số lượng các số trên màn hình ≤ giá trị mà máy ~2~ đưa ra.

Nhiệm vụ của bạn: Sau ~M~ lượt, hãy tính tổng số điểm của Nữ và Nam.

Input

• Dòng ~1~: Một số nguyên dương ~N~ – số lượng số trên màn hình ~(N \leq 10^6)~.
• Dòng ~2~: ~N~ số nguyên dương – các số hiển thị trên màn hình. Mỗi giá trị trên màn hình là số nguyên dương ~\leq 10^6~.
• Dòng ~3~: Một số nguyên dương ~M~ – số lượt chơi ~(M \leq 10^6)~.

• ~M~ dòng tiếp theo: mỗi dòng gồm hai số nguyên ~u~ và ~v~ trong đó:

  • ~u ∈ {0,1}~ là giá trị máy ~1~ xuất ra (xác định ai ghi điểm ở lượt này),
  • ~v~ là giá trị máy ~2~ xuất ra (ngưỡng so sánh) ~(v \leq 10^{15})~.

Output

• Dòng ~1~: tổng điểm của Nữ.
• Dòng ~2~: tổng điểm của Nam.

Sample Input

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

Sample Output

11
8