oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

booksort Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

booksort.html

Mirko has a home library consisting of N books arranged one on top of the other in a narrow cabinet. Since being well trained in the secrets of alphabet in the previous task, he now wishes to arrange the books alphabetically, so that the book whose title comes first alphabetically ends up on top, and the alphabetically last one at the bottom of the pile.

Mirko can easily pull a book out of the cabinet, but it is difficult to push it back into the pile, so the book can only be returned to the top of the pile. Thus, the only available method of sorting the books is repeatedly pulling a book out of the pile and placing it on top of the pile.

The books are labelled with integers from 1 to N, in alphabetical order. Therefore, Mirko wants them to be ordered as (1, 2, ..., N), counting from the top. For example, if N = 3 and the starting order is (3, 2, 1), two moves are sufficient. First, he pulls out the book number 2 and places it on top, so the pile becomes (2, 3, 1). After that, he does the same with book number 1, thus the pile becomes (1, 2, 3).

Help Mirko by calculating the minimum number of moves needed to sort a given starting order! (Source: COCI)

Input

The first line of the input contains the integer N (1 ≤ N ≤ 300,000).

Each of the next N lines contains a single positive integer. These N integers represent the order of Mirko's books from top to bottom of the cabinet. Each of the integers 1,2,...,N appears exactly once.

Output

The first and only line of output must contain the required minimum number of moves.

Sample Input 1

3
3
2
1

Sample Output 1

2

Sample Input 2

4
1
3
4
2

Sample Output 2

2

Tags

Ad Hoc

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1100101s32MBAverage
2011s32MBAverage

Judge Compile Command

g++-8 ans.cpp -o booksort -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.