InfoCNFB 2024 Mirror - Seniori | Minpath

Cerință

Se dă un șir de $n$ numere naturale. Trebuie să scrieți un program care răspunde la interogări de tipul următor: pentru o secvență dată, de lungime putere de $2$, identificată prin indicii $st$ (poziția de început), și $dr$ (poziția de final) dorim să obținem “traseul minimului”.
Acesta se definește este un șir de intervale obținut astfel:

• Primul interval din șir este $st$, $dr$.
• Dacă minimul se află doar în prima jumătate a sa, indicii de început și de final ai acestei jumătăți reprezintă următorul interval din traseu.
• Dacă minimul se află doar în a doua jumătate a sa, indicii de început și de final ai acestei jumătăți reprezintă următorul interval din traseu.
• Dacă minimul se află în ambele jumătăți vom pune în traseu jumătatea cu mai multe apariții ale minimului iar în caz de egalitate, jumătatea din stânga.
• Se continuă pe traseu până se ajunge la un interval de lungime $1$ care conține minimul.

Date de intrare

Fișierul minpath.in conține pe prima linie numărul $n$ și pe a doua linie cele $n$ elemente ale șirului dat (în ordinea indicilor, de la $1$ la $n$).
Pe linia a treia se află numărul de interogări, $t$. Pe fiecare din următoarele $t$ linii se află capetele câte unui interval pentru care avem de aflat traseul minimului.

Date de ieșire

Fișierul minpath.out conține $t$ linii, pe fiecare dintre ele, fiind un număr par de valori reprezentând traseul minimului pentru întrebarea corespunzătoare din fișierul de intrare, astfel: primele două numere sunt capetele stânga respectiv dreapta ale primului interval (chiar cel dat), următoarele două numere sunt capetele stânga respectiv dreapta ale celui de-al doulea interval, și așa mai departe, ultimele două numere sunt egale și reprezintă capetele ultimului interval, cel de lungime $1$.

Restricții și precizări

• $1 \leq n \leq 100 \ 000$;
• Elementele din șirul dat sunt naturale de cel mult nouă cifre.
• $1 \leq t \leq 100 \ 000$;
• Valorile $st$ și $dr$ de la interogări respectă condițiile: sunt ambele cuprinse între $1$ și $n$, $dr-st+1$ este un număr putere de $2$ și $st \leq dr$.

Exemplul 1

minpath.in

10
2 1 4 5 2 3 1 6 1 5
2
1 2
2 9

minpath.out

1 2 2 2
2 9 6 9 6 7 7 7

Explicație

Explicație pentru interogarea 2 9:
Secvența dată este:
2 1 4 5 2 3 1 6 1 5 Se afișează indicii de început și de final ai ei, $2$ și $9$.
Minimul se află în ambele jumătăți, dar de mai multe ori în a doua
2 1 4 5 2 3 1 6 1 5 Se afisează indicii de început și de final ai ei, $6$ și $9$.
În aceasta minimul se află în ambele jumătăți în mod egal, deci se continuă doar în cea stângă
2 1 4 5 2 3 1 6 1 5 Se afișează capetele ei, $6$ și $7$.
Minimul se află în dreapta
2 1 4 5 2 3 1 6 1 5 Ajungem la un interval de lungime $1$, îi afișăm capetele și ne oprim.