DRŽAVNO NATJECANJE 2013. – Drugi dan natjecanja / Srednja škola, I. podskupina (1. i 2. razred) - 3. zadatak

Mirko je veliki ljubitelj brojeva, posebice onih koje smatra lijepima.

Za našeg su junaka lijepi brojevi oni koji u svom dekadskom zapisu sadrže samo znamenke 1 i 9.

Štoviše, nedavno je izjavio da je toliko zaljubljen u lijepe brojeve da može na prvi pogled reći je li zbroj neka dva broja lijep broj.

Skeptični Slavko čuo je ovu izjavu te je odlučio staviti Mirkovu tvrdnju na test.

Napisao je niz od N različitih brojeva, te niz od Q pitanja.

Svako pitanje se sastoji od dva prirodna broja Ai i Bi - koji predstavljaju pozicije u Slavkovom nizu.

Odgovor na pitanje je ukupan broj različitih parova brojeva koji se oba nalaze između Ai-te pozicije i Bi-te pozicije (uključujući i ove dvije pozicije), takvih da je njihova suma lijep broj.

Dva para brojeva razlikuju ukoliko se razlikuju kao dvočlani skup (dakle parove (X, Y) i (Y, X) brojimo samo jednom).

Ako je, na primjer, zadan niz (1, 4, 3, 5, 7, 2, 8, 9, 6) i pitanje (1, 4) onda je odgovor 1 jer između prvog i četvrtog elementa u nizu samo par (4, 5) zadovoljava uvjet.

Napišite program koji će za zadani niz različitih brojeva i pitanja pronaći odgovore na sva pitanja.

Ulazni podaci

U prvom retku ulaza nalazi se prirodni broj N (1 ≤ N ≤ 100 000), duljina niza koji je Slavko napisao.

U drugom retku nalazi se N brojeva Ai (0 ≤ Ai ≤ 100 000) od kojih se sastoji Slavkov niz.

Brojevi u nizu će biti različiti, odnosno niti jedan broj se neće pojaviti više od jedanput.

U trećem retku nalazi se broj Q (1 ≤ Q ≤ 100 000), broj pitanja.

U sljedećih Q redaka nalaze se po dva broja Ai i Bi (1 ≤ Ai ≤ Bi ≤ N) koji opisuju i-to pitanje.

Izlazni podaci

U svaki Q redaka ispisati po jedan broj – odgovor na odgovarajuće pitanje, onim redoslijedom kojim su zadani na ulazu.

Primjeri test podataka

Ulaz

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

Izlaz

1
2
3

Ulaz

10
3 20 0 71 46 53 67 9 24 16
5
5 10
4 6
2 3
5 9
2 5

Izlaz

2
1
0
2
1