1783 - Find Min

Cerința

Se dă un șir P de lungime N cu elemente distincte din mulțimea {1,2..,N}. Pentru fiecare poziție i din șirul P se cere să aflați cea mai mică poziție j, astfel încât P[j] < P[i] și j < i. În caz că o astfel de poziție nu există se consideră -1 ca soluție.

Date de intrare

Fișierul de intrare findmin.in conţine pe prima linie N, reprezentând lungimea șirului iar pe a doua linie N numere naturale, reprezentând elementele șirului P.

Date de ieșire

Fișierul de ieșire findmin.out va conține pe prima linie N numere despărțite prin câte un spațiu, unde al i-lea număr reprezintă răspunsul pentru al i-lea element din șir.

Restricții și precizări

• 1 ≤ N ≤ 1 000 000

• Șirul P este indexat de la 1.

Exemplu 1

Intrare

7

5 6 7 3 1 4 2

Ieșire

-1 1 1 -1 -1 4 5

Explicație

Pentru primele 2 elemente răspunsurile sunt -1 respectiv 1. Pentru al 3-lea element răspunsul e poziția 1(se observă că și P[2] < P[3]). Pentru elementele de pe pozițiile 4 și 5 răspunsurile sunt: -1 și -1. Răspunsul pentru al 6-lea element: poziția 4 (se observa că și P[5] < P[6]). În final, răspunsul pentru ultimul elementul: poziția 5.

Exemplu 2

Intrare

1000001

1 2 3 3 3

Ieșire

Date de intrare gresite!

Rezolvare

#1783 Find Min
def conditii(n, sir_p):
    restrictii = (
        1 <= min(sir_p),
        max(sir_p) <= 1_000_000,
        1 <= n <= 1_000_000,
        len(sir_p) == n
    )

    return all(restrictii)


def gasire_min(numere):
    sir = []

    for i in range(len(numere)):
        minim = 1_000_001
        for j in range(i):
            if numere[j] < numere[i]:
                if numere[j] < minim:
                    minim = j
        sir.append(f"{minim+1 if minim != 1_000_001 else -1}")

    return " ".join(sir)


def main():
    n = int(input())
    sir_p = [int(x) for x in input().split()]
    if not conditii(n, sir_p):
        return print("Date de intrare gresite!")

    print(gasire_min(sir_p))


if __name__ == "__main__":
    main()