codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

605A.md (1330B)


      1 Source: https://codeforces.com/problemset/problem/605/A
      2 
      3 A. Sorting Railway Cars
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 An infinitely long railway has a train consisting of *n* cars, numbered from 1 to *n* (the numbers of all the cars are distinct) and positioned in arbitrary order. David Blaine wants to sort the railway cars in the order of increasing numbers. In one move he can make one of the cars disappear from its place and teleport it either to the beginning of the train, or to the end of the train, at his desire. What is the minimum number of actions David Blaine needs to perform in order to sort the train?
     22 
     23 Input
     24 
     25 The first line of the input contains integer *n* (1 ≤ *n* ≤ 100 000) — the number of cars in the train.
     26 
     27 The second line contains *n* integers *p**i* (1 ≤ *p**i* ≤ *n*, *p**i* ≠ *p**j* if *i* ≠ *j*) — the sequence of the numbers of the cars in the train.
     28 
     29 Output
     30 
     31 Print a single integer — the minimum number of actions needed to sort the railway cars.
     32 
     33 Examples
     34 
     35 Input
     36 
     37 ```
     38 5  
     39 4 1 2 5 3
     40 ```
     41 
     42 Output
     43 
     44 ```
     45 2
     46 ```
     47 
     48 Input
     49 
     50 ```
     51 4  
     52 4 1 3 2
     53 ```
     54 
     55 Output
     56 
     57 ```
     58 2
     59 ```
     60 
     61 Note
     62 
     63 In the first sample you need first to teleport the 4-th car, and then the 5-th car to the end of the train.