Numim inserare a unui șir A într-un șir B introducerea, între două elemente ale șirului B, a tuturor elementelor lui A, pe poziții consecutive, în ordinea în care apar în A.

Se dau două șiruri cu n, respectiv m elemente numere întregi ordonate strict crescător, în care numerotarea elementelor începe de la 1.

Se cere să se afișeze poziția din al doilea șir începând de la care poate fi inserat primul șir, astfel încât șirul obținut să fie strict crescător. Dacă nu există o astfel de poziție, se afișează mesajul imposibil.

Date de intrare

Fișierul de intrare inserare2.in conține numere naturale din intervalul [1,106]: pe prima linie numerele m și n, iar pe fiecare dintre următoarele două linii câte un șir de m, respectiv de n numere întregi ordonate strict crescător. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire inserare2.out va conține poziția din al doilea șir începând de la care poate fi inserat primul șir, astfel încât șirul obținut să fie strict crescător. Dacă nu există o astfel de poziție, se afișează mesajul imposibil.

Restricții și precizări

• Proiectați un algoritm eficient din punctul de vedere al spațiului de memorie utilizat și al timpului de executare.
  • se recomandă o soluție care să nu memoreze cel două șiruri în tablouri sau alte structuri de date similare.

Exemplul 1

inserare2.in

4 6
15 16 17 19
7 10 12 20 30 40

inserare2.out

4

Explicație

Se poate obține șirul 7, 10, 12, 15, 16, 17, 19, 20, 30, 40.

Exemplul 2

inserare2.in

4 6
15 16 17 19
7 14 18 20 30 40

inserare2.out

imposibil

Exemplul 3

inserare2.in

4 6
1 2 3 4
7 14 18 20 30 40

inserare2.out

imposibil

#include <fstream>
using namespace std;
ifstream cin("inserare2.in");
ofstream cout("inserare2.out");

int main()
{
    int n,m,x,primul=0,ultimul=0,precedent,ok=0,poz=0;
    cin>>m;
    cin>>n;
    cin>>x;
    primul=x;
    for(int i=2;i<=m;i++)
    {
        cin>>x;
        ultimul=x;
    }
    cin>>x;
    precedent=x;
    for(int i=2;i<=n && ok==0;i++)
    {
        cin>>x;
        if(primul>precedent && ultimul<x)
        {
            poz=i;
            ok=1;
        }
        precedent=x;
    }
    if(poz==0)
        cout<<"imposibil";
    else
       cout<<poz;
    return 0;

}