Informática Avançado - Semana 52 - Problema 1

Para Frente e para trás

 
Sams adora permutações, e por isso, ela criou um novo jogo em homenagem a elas. O jogo funciona da seguinte maneira: Será dada uma permutação de tamanho N (N \leq 10^5), na qual é permitido fazer qualquer uma das seguintes operações:

  • Escolher um elemento qualquer e posicioná-lo no início da permutação
  • Escolher um elemento qualquer e posicioná-lo no final da permutação

Sams quer que você responda a seguinte pergunta: Qual é o número mínimo de operações necessárias para deixar a permutação em ordem crescente?

Entrada

A primeira linha consiste de um inteiro N. A segunda linha contém N números, a permutação inicial.

Saída

Imprima um único inteiro: A resposta da pergunta de Sams.

Exemplo

ENTRADA SAÍDA
6
6 3 2 4 5 1
3