A folytatás sohasem olyan jó, mint az eredeti. Rendszeresen találkozunk olyan filmfolytatásokkal, amelyek során nem értjük, hogy az eredeti miért olyan sikeres, viszont a folytatásuk unalmas, szokványos vagy egyenesen rossz lesz. Mi persze igyekezünk, hogy ezt a felfogást megváltoztassuk, ezért bemutatjuk a tavalyi sikertörténet folytatását: „Aranypénz 2: Electric Boogaloo”.

Midász király egy számegyenest tart maga előtt. Ezen az egyenesen, \(N\) különböző egész számú koordinátán, egy-egy aranypénz helyezkedik el. Azt a játékot játssza, hogy egy mozdulattal elmozgat egy aranypénzt a számegyenesen a szomszédos pozícióra ( \(x\) -ről \(x+1\)-re vagy \(x-1\)-re). Ugyanazon a pozíción egy időben sohasem lehet két aranypénz. Midász az aranypénzeket egymás mellé szeretné helyezni, de még nem tudja, hogyan teheti ezt meg. Ezért összesen \(Q\) forgatókönyvet vizsgál meg játékához. Minden forgatókönyv egy \(x\) számmal van megadva. Az adott forgatókönyv szerint Midász célja az, hogy az aranypénzeket áthelyezze úgy, hogy azok az \(\{x,x+1,\cdots,x+N-1\}\) halmaz különböző pozícióin helyezkedjenek el. A forgatókönyvek egymástól függetlenek, vagyis az aranypénzek mindig ugyanarról a pozíciókról indulnak.

Midász király titeket kért meg arra, hogy segítsetek neki megtalálni az elmozgatások minimális számát, amellyel befejezheti a játékot egy adott forgatókönyv esetén. Ha ő maga is tudná a megoldást, a feladat nem is lenne egy jó feladat.

Bemenet

Az első sorban \(N\) természetes szám, az aranypénzek száma helyezkedik el. A második sorban \(N\) egész szám \(a_1<a_2<\cdots<a_N\) számok, az aranypénzek pozíciói találhatók növekvő sorrendben. A harmadik sorban a \(Q\) szám, a forgatókönyvek száma található. A következő \(Q\) sorban egy-egy \(x\) szám áll, amelyekkel a forgatókönyvek adottak.

Kimenet

A kimeneten kiíratni \(Q\) számot, ahol az \(i\)-edik szám az elmozgatások minimális számát jelenti, amellyel Midász király be tudja fejezni játékát az \(i\)-edik forgatókönyv esetén.

Korlátozások

• \(1 \leq N,Q \leq 200.000\)
• \(0 < a_1<a_2<\cdots<a_N \le10^9\)
• \(0<x\le10^9\) minden lekérdezés esetén

A tesztpéldák 4 független csoportba oszthatók:

• Tesztpéldák, melyek \(10\) pontot érnek: \(N = 1\).
• Tesztpéldák, melyek \(10\) pontot érnek: \(N,Q\leq 1000\), \(a_i\le 100.000\) és \(x\le 100.000\) minden forgatókönyvre.
• Tesztpéldák, melyek \(30\) pontot érnek: \(a_i=p+i\cdot d\), vagyis az aranypénzek kezdőpozíciói matematikai sorozatot képeznek.
• Tesztpéldák, melyek \(50\) pontot érnek: nincs külön korlátozás.

Példák

1. példa

Bemenet

2
2 4
2
5
2

Kimenet

5
1

Magyarázat

Az első forgatókönyv esetén a második aranypénzt \(2\) hellyel jobbra mozgatjuk (a \(4\)-ről a \(6\)-ra), az első aranypénzt pedig \(3\) hellyel jobbra (a \(2\)-ről az \(5\)-re) mozgatjuk. A második forgatókönyv esetén elegendő a második aranyat egy hellyel balra mozgatni.