Minimizing Moves for Giraffe Reordering

IOI Zoo is famous for its giraffes. There are \(N\) giraffes with distinct heights, numbered from \(1\) to \(N\) in increasing order of height. The zoo has \(N\) cages arranged in a row (from left to right numbered \(1\) to \(N\)), and each cage contains exactly one giraffe. Initially, cage \(i\) holds giraffe \(P_i\) (where the permutation \(P\) is given).

When a visitor takes a photo, they choose two integers \(l\) and \(r\) (with \(1 \le l \le r \le N\)) and photograph all giraffes in cages \(l, l+1, \ldots, r\). The photo is considered bad if both of the following conditions are satisfied:

• There exists an index \(k\) with \(l < k < r\) such that the giraffe in position \(k\) is taller than those in positions \(l\) and \(r\), i.e. \(P_l P_r\).
• There exists an index \(k\) with \(l < k P_k < P_r\).

Mr. APIO, the zoo director, wants to rearrange the giraffes so that for any choice of \(l\) and \(r\), the photo is never bad. Since moving a giraffe from one cage to another is laborious and each cage must contain exactly one giraffe after the rearrangement, he wants to minimize the number of giraffes that need to be moved.

Observation: A sufficient way to avoid a bad photo is to have the giraffes arranged in a monotonic order (either strictly increasing or strictly decreasing). In such orders, for every contiguous segment (with at least 3 cages), there is no internal giraffe that is both a peak and a valley with respect to the endpoints. Therefore, one approach is to rearrange all giraffes into sorted order (increasing or decreasing). To minimize the moves, Mr. APIO should retain as many giraffes as possible that are already in the correct order. In other words, the answer is given by:

[ \text{Answer} = N - \max(\text{LIS},, \text{LDS}) ]

where \(\text{LIS}\) is the length of the longest increasing subsequence of \(P\) and \(\text{LDS}\) is the length of the longest decreasing subsequence of \(P\). Your task is to compute the minimum number of moves required.

inputFormat

The first line contains an integer \(N\) \( (1 \le N \le 10^5)\). The second line contains \(N\) distinct integers \(P_1, P_2, \ldots, P_N\), representing the current arrangement of giraffes.

outputFormat

Output a single integer: the minimum number of giraffes to move so that no contiguous segment will form a bad photo.

sample

3
1 3 2

1