Editing 2939 - Permutari4

= Cerința =
O permutare de ordin <code>K</code> este formată din toate numerele <code>1</code>, <code>2</code>, …, <code>K</code> nu neapărat în această ordine.

O secvență de lungime <code>L</code> este formată din <code>L</code> elemente ale șirului aflate pe poziții consecutive. Spunem că o secvență de lungime <code>L</code> este permutare de ordin <code>L</code> dacă ea conține toate numerele <code>1</code>, <code>2</code>, …, <code>L</code>, nu neapărat în această ordine.

Se dă un șir de <code>N</code> numere naturale nenule , ce reprezintă o permutare de ordin <code>N</code>. Să se calculeze numărul secvențelor din șirul <code>a</code> care au proprietatea că sunt permutări.

= Date de intrare =
Fișierul de intrare <code>input.txt</code> conține pe prima linie numărul natural <code>N</code>, iar pe a doua linie se află primele <code>N</code> numere naturale nenule, separate prin spațiu. Cele <code>N</code> numere date nu sunt obligatoriu în ordine strict crescătoare.

= Date de ieșire =
În fișierul de ieșire <code>output.txt</code> se va scrie un singur număr natural reprezentând numărul secvențelor de tip permutare care apar în şirul dat.

= Restricții și precizări =

* <code>1 < N ≤ 100.000</code>

== Exemplul 1 ==
input.txt:

7

4 2 5 1 3 7 6

output.txt:

3

Explicație:

În şir există <code>3</code> secvențe de tip permutare, de lungimi <code>1, 5 şi 7</code>:

<code>1</code>

<code>4 2 5 1 3</code>

<code>4 2 5 1 3 7 6</code>

Nu există secvențe permutare de lungime <code>2</code>, <code>3</code>, <code>4</code> sau <code>6</code>.

== Exemplul 2 ==
input.txt:

9999999999999

4 2 5 1 3 7 6

Output:

Input-ul nu convine conditiilor

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verificare(n):
    if not(1<=n<=100000):
        print("Input-ul nu convine conditiilor")
        exit()

f=open("input.txt","r")
w=open("output.txt","w")

n=f.readline().split()
n=int(n[0])
verificare(n)
q={}
r=0
v=f.readline().split()
for i in range(len(v)):
    q[int(v[i])]=i+1
if 1 not in q:
    q[1]=0
if q[1]!=0:
    r+=1
a=q[1]
b=q[1]
for i in range(1,len(v)):
    if i not in q:
        q[i]=0
    if q[i]<a:
        a=q[i]
    if q[i]>b:
        b=q[i]
    if b-a+1==i:
        r+=1
w.write(str(r))
w.close()
</syntaxhighlight>