Bubble Sort

Bubble Sort

Bubble sort is one of the algorithms for sorting columns. Suppose you want to sort the sequence A of length N in ascending order. Bubble sort exchanges the positions of two adjacent numbers if the magnitude relationship is broken. This is done while scanning the sequence from the front. That is, if there is a place where Ai> Ai + 1, the two numbers are exchanged once for i = 1, 2, ..., N − 1 in this order. It is a scan of. It is known that the sequence can be sorted in ascending order by repeating this scan N − 1 time.

The number of exchanges by bubble sort in sequence A is the number of times integers are exchanged when the above algorithm is applied to sequence A. (Algorithms and implementations known as bubble sort may have small differences in loop order, range, end conditions, etc. However, the number of integer exchanges when applied to the same sequence depends on those differences. It is known that it does not change.)

For example, the following program describes a function that sorts an array a of integers of length n by bubble sort in C language.

void bubble_sort (int * a, int n) { int i, j; for (i = 0; i <n -1; ++ i) { for (j = 0; j <n -1; ++ j) { if (a [j]> a [j + 1]) { / * The following 3 lines are equivalent to one integer exchange * / int x = a [j]; a [j] = a [j + 1]; a [j + 1] = x; } } } }

Task

Given a sequence A of length N. Suppose you create a sequence A'by exchanging two integers anywhere in the sequence A only once. Create a program that finds the minimum number of exchanges by bubble sort in the sequence A'. (Note that the first two integers to be exchanged do not necessarily have to be next to each other.)

Limits

• 1 ≤ N ≤ 100 000 Length of sequence A
• 1 ≤ Ai ≤ 1 000 000 000 The size of the numbers in the sequence A

input

Read the following data from standard input.

• The integer N is written on the first line. N represents the length of the sequence A.
• The integer Ai is written on the i-th line (1 ≤ i ≤ N) of the following N lines. This represents the i-th integer in the sequence A.

output

Output to the standard output an integer representing the minimum number of exchanges by bubble sort in the sequence A'on one line.

Scoring criteria

• Of the scoring data, 10% of the points are satisfied with N ≤ 1 000, and Ai ≠ Aj is satisfied with any i, j (1 ≤ i <j ≤ N).
• Of the scoring data, 30% of the points are satisfied with N ≤ 5 000, and Ai ≠ Aj is satisfied for any i, j (1 ≤ i <j ≤ N).
• Of the scoring data, 80% of the points are given by satisfying Ai ≠ Aj for any i, j (1 ≤ i <j ≤ N).

Input / output example

Input example 1

Five Ten 3 6 8 1

Output example 1

0

If we decide to exchange the first 10 and the last 1 of the sequence A, the sequence A'will be a sorted column and the number of bubble sort exchanges will be 0.

Input example 2

Five 3 1 7 9 Five

Output example 2

2

By exchanging the third 7 and the last 5 of the sequence A, the sequence A'becomes 3,1,5,9,7. The number of exchanges of A'by bubble sort is 2.

Input example 3

3 1 2 3

Output example 3

1

Even if the sequence A is sorted from the beginning, it must be exchanged when creating the sequence A'.

The question text and the data used for the automatic referee are the question text and the test data for scoring, which are created and published by the Japan Committee for Information Olympics.

Example

Input

5 10 3 6 8 1

Output

0

inputFormat

input

Read the following data from standard input.

• The integer N is written on the first line. N represents the length of the sequence A.
• The integer Ai is written on the i-th line (1 ≤ i ≤ N) of the following N lines. This represents the i-th integer in the sequence A.

outputFormat

output

Output to the standard output an integer representing the minimum number of exchanges by bubble sort in the sequence A'on one line.

Scoring criteria

• Of the scoring data, 10% of the points are satisfied with N ≤ 1 000, and Ai ≠ Aj is satisfied with any i, j (1 ≤ i <j ≤ N).
• Of the scoring data, 30% of the points are satisfied with N ≤ 5 000, and Ai ≠ Aj is satisfied for any i, j (1 ≤ i <j ≤ N).
• Of the scoring data, 80% of the points are given by satisfying Ai ≠ Aj for any i, j (1 ≤ i <j ≤ N).

Input / output example

Input example 1

Five Ten 3 6 8 1

Output example 1

0

If we decide to exchange the first 10 and the last 1 of the sequence A, the sequence A'will be a sorted column and the number of bubble sort exchanges will be 0.

Input example 2

Five 3 1 7 9 Five

Output example 2

2

By exchanging the third 7 and the last 5 of the sequence A, the sequence A'becomes 3,1,5,9,7. The number of exchanges of A'by bubble sort is 2.

Input example 3

3 1 2 3

Output example 3

1

Even if the sequence A is sorted from the beginning, it must be exchanged when creating the sequence A'.

The question text and the data used for the automatic referee are the question text and the test data for scoring, which are created and published by the Japan Committee for Information Olympics.

Example

Input

5 10 3 6 8 1

Output

0

样例

5
10
3
6
8
1

0