Everyone is aware of the \(6\) infinity stones that exist in Marvel Cinematic Universe (MCU) and are in the possession of mighty Thanos. There is one problem though the stones are arranged randomly on his giant hand and he needs them to be arranged in increasing order of their respective powers so that he could use them according to the demand of the situation.

Seems quite simple, isnt it? But this isn't MCU, this is our CPU (Competitive Programming Universe), the situation here is more complicated:

1. There are \(N\) infinity stones on CPU with powers ranging from \(1\) to \(N\). You will be given a permutation \((A_1, A_2, A_3,...A_N)\) of these \(N\) distinct integers.

2. For arranging the elements you can perform following operation -

**Pick an element**of the sequence and**move**it to the**beginning**or**ending**of the sequence.

Thanos has less than \(12\) days left to prepare for the big fight, but you have only 5 hours to find the minimum number of operations required to get the job done.

**INPUT FORMAT:**

First line of input contains a single integer \(N\) denoting the no. of infinity stones.

Next \(N\) lines contain a single integer each denoting the power of \(i^{th}\) stone.

**OUTPUT FORMAT:**

Print the **minimum** number of operations required.

**CONSTRAINTS:**

\(1 \leq N ≤ 2×10^{5} \\ A_1, A_2, A_3,...A_N\ is\ a\ permutation\ of\ (1, 2,...N)\)

Explanation

For example, the sequence can be sorted in ascending order as follows:

- Move 2 to the beginning. The sequence is now (2,1,3,4)
- Move 1 to the beginning. The sequence is now (1,2,3,4)

Time Limit:
1.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Marking Scheme:
Marks are awarded when all the testcases pass.

Allowed Languages:
Bash,
C,
C++,
C++14,
C++17,
Clojure,
C#,
D,
Erlang,
F#,
Go,
Groovy,
Haskell,
Java,
Java 8,
Java 14,
JavaScript(Rhino),
JavaScript(Node.js),
Julia,
Kotlin,
Lisp,
Lisp (SBCL),
Lua,
Objective-C,
OCaml,
Octave,
Pascal,
Perl,
PHP,
Python,
Python 3,
Python 3.8,
R(RScript),
Racket,
Ruby,
Rust,
Scala,
Swift-4.1,
Swift,
TypeScript,
Visual Basic

Initializing Code Editor...

{"c06f897": "/pagelets/recommended-problems/algorithm/thanos-and-the-infinity-stones/", "4ebbdf7": "/pagelets/problem-author-tester/algorithm/thanos-and-the-infinity-stones/", "1d9092b": "/pagelets/problems-hint/algorithm/thanos-and-the-infinity-stones/", "1e9ce56": "/pagelets/show-submission/algorithm/thanos-and-the-infinity-stones/"}