ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

USU Internal Contest March'2003

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. Sorting the Tombstones

Time limit: 1.0 second
Memory limit: 64 MB
There is time to throw stones and there is time to sort stones…
An old desolate cemetery is a long dismal row of nameless tombstones There are N tombstones of various shapes. The weights of all the stones are different. People have decided to make the cemetery look more presentable, sorting the tombstone according to their weight (in increasing or decreasing order). The local custom allows to transpose stones if there are exactly K other stones between them.

Input

The first input line contains an integer N (1 ≤ N ≤ 130000). Each of the next N lines contains an integer X, the weight of a stone in grams (1 ≤ X ≤ 130000).

Output

The output should contain the single integer — the maximal value of K (0 ≤ K < N), that makes possible the sorting of the stones according to their weights.

Sample

inputoutput
5
30
21
56
40
17
1
Problem Author: Alexey Lakhtin
Problem Source: Open collegiate programming contest for student teams, Ural State University, March 15, 2003
To submit the solution for this problem go to the Problem set: 1252. Sorting the Tombstones