All Tracks Data Structures Hash Tables Basics of Hash Tables Problem

Infinity Permutations
Tag(s):

Easy, Sorting, subsequence

Problem
Editorial
Analytics

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)\)

SAMPLE INPUT
4
1
3
2
4
SAMPLE OUTPUT
2
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, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications

?