Problem : 282 - Empire disruption

Problem Statistics

Solved Member: 13　　Submission: 29　　User Tried: 18

Statement:

瀚瀚國一共有 m 個城市，這 m 個城市排列成一條線，依序編號為 1,2,3,...,m。

但是最近瀚瀚國發生政變，瀚瀚國國王瀚瀚非常困擾，m 個城市當中只剩下 n 個城市在瀚瀚的控制範圍內。

為此，瀚瀚決定對其他的城市實行痴漢(?)式清略，他準備了 q 種計畫，每一種計畫用兩個整數 x,y 來表示。每次侵略會以每一個控制的城市為中心，以每個城市 a 為中心去攻打並佔領編號 a-x, a-x+1, a-x+2,..., a-1, a, a+1, a+2,..., a+y 的城市(若存在的話)。

但是由於計畫數量太多了，他想知道每一種計畫執行結束之後，他所佔領的城市數量會有多少個。請你幫他算算看吧！

例如 m=7，而瀚瀚的控制範圍為 2,4 兩個城市。

對於計畫 x=3, y=4，則編號 2 的城市會去佔領 1~6 之間的城市，而編號 4 的城市則會去佔領 1~7 之間的城市。因此計畫結束之後瀚瀚佔領了總共 7 個城市。

而對於計畫 x=3, y=0，編號 2 的城市會去佔領 1~2 之間的城市，而編號 4 的城市則會去佔領 1~4 之間的城市。因此計畫結束之後瀚瀚佔領了總共 4 個城市。

Input:Output:

每一筆輸入的第一行會有三個整數，m, n, q，依序代表總城市數量、瀚瀚控制的城市數量、以及計畫數量。

第二行會有 n 個整數 a₁, a₂, ..., a_n，分別代表瀚瀚控制的城市編號。每個數字皆相異，並且由小到大排列。

接下來的 q 行，每一行會有兩個數字 x,y ，依序代表每一個計畫的敘述。

限制：
1 ≤ m ≤ 1000000000
1 ≤ n ≤ min(m, 100000)
1 ≤ q ≤ 100000
0 ≤ x,y ≤ 1000000000

對於其中 20% 的測試資料滿足： n ≤ 300，m,q ≤ 1000
對於其中 50% 的測試資料滿足： n,q ≤ 2000

請輸出 q 行，每行一個數字。代表每一個計畫執行之後，瀚瀚會佔領的城市數量。

Sample Input:Sample Output:

SAMPLE A:
7 2 3
2 4
1 1
3 0
3 4

SAMPLE B:
100 5 5
3 18 24 57 90
1 8
27 0
15 16
22 3
2 2

SAMPLE A:
5
4
7

SAMPLE B:
46
80
98
79
25

HINT:

敘述中的範例與 SAMPLE A 的其中兩筆詢問是相同的

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0-1	2500ms	131072kb
0-2	2500ms	131072kb
1	2500ms	131072kb	10
2	2500ms	131072kb	10
3	2500ms	131072kb	10
4	2500ms	131072kb	10
5	2500ms	131072kb	10
6	2500ms	131072kb	10
7	2500ms	131072kb	10
8	2500ms	131072kb	10
9	2500ms	131072kb	10
10	2500ms	131072kb	10