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.

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

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.