Out of Sorts (Silver)#10384

Out of Sorts (Silver)

1 secondo

128 megabyte

Media

Tenendo d'occhio le opportunità di carriera a lungo termine al di là della fattoria, la mucca Bessie ha iniziato a studiare algoritmi su vari siti web di programmazione online.

Il suo algoritmo preferito finora è il "bubble sort". Ecco l'implementazione di Bessie, in cow-code, per ordinare un array $A$ di lunghezza $n$ :

sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to n-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
         sorted = false

A quanto pare, il comando "moo" nel cow-code non fa nient'altro che stampare "moo". Stranamente, Bessie insiste nell'includerlo in vari punti del suo codice.

Dato l'array in input, prevedi quante volte il codice di Bessie stamperà "moo".

Input

La prima riga contiene un intero $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5). Ciascuna delle successive $n$ righe contiene un elemento dell'array $A_{0}, \dots, A_{n - 1}$ A_0, \ldots, A_{n-1} — un intero da $0$ a $1 0^{9}$ 10^9. Gli elementi non sono necessariamente distinti.

Output

Stampa un intero — il numero di volte in cui viene stampato "moo".

Esempi

Esempio 1