Editing 3860 - consecutive1

== Enunt ==
Se dă un șir (a[1], a[2], ..., a[n]) de numere naturale cuprinse între 1 și n. Se dau de asemenea Q interogări, fiecare prin două numere x, y: dacă s-ar ordona a[x], a[x+1], ..., a[y], se obține sau nu o secvență de numere consecutive? (De exemplu, 5,3,6,4 dacă e ordonată se obține 3,4,5,6, care este o secvență de numere consecutive).
== Cerinţa ==
Dându-se Q întrebări, să se răspundă la acestea. La fiecare interogare, dacă prin sortare se obține o secvență de numere consecutive veți afișa valoarea 1, iar în caz contrar veți afișa valoarea 0.
== Date de intrare ==
De la tastatură, de pe prima linie se citește numărul natural n. Pe linia a doua se află n numere naturale reprezentând elementele șirului. Pe a treia linie se află numărul Q, iar pe următoarele Q linii se găsesc câte două numere naturale x și y, 1 ≤ x ≤ y ≤ n, reprezentând câte o interogare.
== Date de ieșire ==
La ecran se vor afișa pe o singură linie, fără spații, Q cifre din mulțimea {0, 1} reprezentând răspunsurile la fiecare întrebare.
== Restricţii şi precizări ==
* Pentru 10 puncte, 3 ≤ n ≤ 50, 1 ≤ Q ≤ 100
* Pentru 30 puncte, n ≤ 300, Q ≤ 10.000
* Pentru 60 puncte, 10.000 ≤ n ≤ 100.000, Q ≤ 200.000
== Exemplu ==
; Intrare
 9
 4 1 3 4 2 1 6 5 4
 5
 1 4
 3 5
 3 6
 5 9
 7 9
; Ieșire
 01101
<br>

== Explicație ==
Sunt 5 interogări.
Întrebarea 1: 4 1 3 4 nu obține o secvență de numere consecutive, deci răspunsul este 0.
Întrebarea 2: 3 4 2 obține o secvență de numere consecutive, deci răspunsul este 1.
Întrebarea 3: 3 4 2 1 obține o secvență de numere consecutive, deci răspunsul este 1.
Întrebarea 4: 2 1 6 5 4 nu obține o secvență de numere consecutive, deci răspunsul este 0.
Întrebarea 5: 6 5 4 obține o secvență de numere consecutive, deci răspunsul este 1.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def can_form_consecutive_sequence(arr, x, y):
    sorted_arr = sorted(arr[x-1:y])
    for i in range(1, len(sorted_arr)):
        if sorted_arr[i] != sorted_arr[i-1] + 1:
            return False
    return True

def main():
    n = int(input())
    arr = list(map(int, input().split()))
    Q = int(input())

    result = ""
    for _ in range(Q):
        x, y = map(int, input().split())
        result += "1" if can_form_consecutive_sequence(arr, x, y) else "0"

    print(result)

if __name__ == "__main__":
    main()

</syntaxhighlight>