308 . 數字遊戲

Description

Alice 跟 Bob 在玩遊戲，給定 $a_1,a_2,\dots ,a_{2N}$$a_1, a_2, \ldots, a_{2N}$，Alice 可以將這個數列任意排列，之後 Bob 要做最少次操作使得 $a_i=a_{i+N}$$a_{i} = a_{i+N}$ 對所有 $i$$i$ 從 $1$$1$ 到 $N$$N$ 都成立，Bob 每次可以進行的操作為選擇一個足標 $i$$i$，將 $a_i$$a_i$ 改成 $\lfloor \frac{a_i}{2}\rfloor ,2a_i$$\lfloor \frac{a_i}{2} \rfloor,2a_i$ 或 $2a_i+1$$2a_i+1$。Alice 想讓 Bob 需要的操作次數盡量多，那最多可以是多少？

因為這遊戲對他們來說實在太簡單，所以他們決定改成以下問題：Alice 會進行 $Q$$Q$ 次挑戰，每一次挑戰都會選擇數列的某個數修改成新的數字，請 Bob 在每次修改後告訴 Alice 上述遊戲的答案是多少。請注意在過程中真正會改變序列的只有這 $Q$$Q$ 次修改。

Input Format

輸入第一行包含一個正整數 $N$$N$ ，代表數列有 $2N$$2N$ 個數字。

接下來的一行輸入 $2N$$2N$ 個數字，第 $i$$i$ 個數字代表一開始的 $a_i$$a_i$。

接下來的一行包含一個正整數 $Q$$Q$ ，代表有 $Q$$Q$ 個修改操作。

接下來有 $Q$$Q$ 行，第 $i$$i$ 行有兩個以空白分隔的整數 $x_i,y_i$$x_i,y_i$，代表要將第 $x_i$$x_i$ 個數字改成 $y_i$$y_i$。

• $1\le N,Q\le {10}^5$$1 \leq N, Q \leq 10^ 5$

• $1\le a_i,y_i\le {10}^6$$1 \leq a_i, y_i \leq 10^ 6$

• $1\le x_i\le 2N$$1 \leq x_i \leq 2N$

Output Format

請輸出 $Q$$Q$ 行數字，第 $i$$i$ 行數字代表在第 $i$$i$ 次修改之後的答案。

Sample Input 1

xxxxxxxxxx
3
2 8 6 2 5 4
3
5 7
2 10
1 6

Sample Output 1

xxxxxxxxxx
9
9
12

Sample Input 2

xxxxxxxxxx
3
6 8 4 4 7 7
3
2 9
3 8
2 9

Sample Output 2

xxxxxxxxxx
13
14
14

Sample Input 3

xxxxxxxxxx
5
7 3 8 7 6 2 5 1 6 6
5
2 5
5 1
2 4
10 2
8 9

Sample Output 3

xxxxxxxxxx
18
16
16
15
16

Subtasks

Testdata and Limits