Fie un şir a cu n elemente: a=(a[1], a[2], …, a[n]). Vom numi un punct fix al şirului orice element de pe o poziţie i care are proprietatea că a[i]=i.
De exemplu următorul şir cu 7 elemente a=(-3,-2, 1, 3, 4, 6, 10) are un singur punct fix i=6, pentru că a[6]=6.
Vom defini translaţia şirului cu o valoare v şirul obţinut prin adunarea la fiecare element din şir a valorii v; şirul obţinut se notează cu a{v}. În mod evident a{0}=a (adică şirul translatat cu valoarea 0 este chiar şirul iniţial).
Translaţia poate fi realizată atât cu o valoare pozitivă, cât şi cu o valoare negativă. Dacă aplicăm o translaţie cu valoarea 3 asupra şirului de mai sus vom obţine a{3}=(0,1,4,6,7,9,13). Observăm, că a{3} nu are niciun punct fix. Aplicând asupra şirului o translaţie de valoare -3, vom obţine a{-3}=(-6,-5,-2,0,1,3,7). Şirul translatat a{-3} are un punct fix în punctul 7 pentru că a{-3}[7]=7.
Cerinţă
Scrieţi un program care citeşte un şir a cu n elemente şi un şir de translaţii, şi calculează pentru fiecare translaţie numărul de puncte fixe. Şirul pe care îl vom verifica întotdeauna este strict crescător. Şirul translaţiilor nu este ordonat.
Date de intrare
Fişierul de intrare punctfix.in conţine pe prima linie valoarea lui n. Pe linia a doua se vor găsi n numere naturale a[1] a[2] ... a[n] separate prin spaţii, ordonate strict crescător. Linia a treia conţine valoarea k, iar pe linia a patra vom avea k numere întregi separate prin spaţiu v[1] v[2] ... v[k], corespunzătoare celor k translaţii.
Date de ieşire
Fişierul de ieşire punctfix.out va conţine k linii. Pe linia i se va tipări numărul de puncte fixe ale şirului translatat a{v[i]}, pentru 1≤i≤k.
Restricţii
• 2 ≤ n ≤ 10 000
• -1 000 000 000 ≤ a[i] ≤ 1 000 000 000, pentru 1 ≤ i ≤ n
• 1 ≤ k ≤ 150 000
• -1 000 000 000 ≤ v[i] ≤ 1 000 000 000, pentru 1 ≤ i ≤ k
• max(a[i])-min(a[i])≤ 100000
• max(v[i])-min(v[i])≤ 100000
• Elementele şirului a sunt ordonate strict crescător.
• Elementele şirului v pot fi în orice ordine, valorile elementelor de pe diferite poziţii pot fi egale sau distincte.
• Fiecare translaţie se aplică şirului iniţial.
Exemple
punctfix.in
punctfix.out
Explicaţii
7
-3 -2 1 3 4 6 10
7
0 3 -3 4 2 -3 1000
1
0
1
2
1
1
0
translaţie cu 0, avem un punct fix: a{0}[6]=6
translaţie cu 3, nu avem elemente cu proprietatea a{3}[i]=i
translaţie cu -3, avem un punct fix: a{-3}[7]=7
translaţie cu 4, avem două puncte fixe: a{4}[1]=1, a{4}[2]=2
translaţie cu 2, avem un punct fix: a{2}[3]=3
translaţie cu -3, avem un punct fix: a{-3}[7]=7
translaţie cu 1000, nu avem elemente cu proprietatea a{1000}[i]=i