该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

众所周知 李华是一个非常严谨的人，他喜欢一切带有规律的事物，有一天他在学习编程的时候遇到了好多数组，这些数组太多了，李华十分的偏心，他只希望处理那些有规律的数组：

• 若一个数组严格单调递增或者严格单调递减，那么李华就认为他是有规律的

但是李华深知自己的缺点，所以李华决定弥补这个缺点但是又不想耗费太多的尽力，于是他想到了一个方案

• 对于该数组李华可以操作一次，重新排列其中一段连续的元素。并且耗费的精力是这段连续元素的长度 ：比如你重新排列的是区间[1,2] 那么花费的精力就是 2。

然而李华的精力十分的有限。他想知道最少需要多少精力去将该数组变为他喜欢的数组。 这个问题太复杂了所以李华找到了聪明的你来解决这个问题。

输入描述

第一行两个整数 n 。

第二行 n个整数 用空格隔开。

输入范围

对于%40的数据 $1 <= n <= 10^3$

对于%60的数据 $1 <= n <= 10^5$

对于数组里的元素 a[i] : $1 <= a[i] <= n$

数组的数据保证，区间[1 ,n]的数每个出现一次

输出

输出需要的最少的精力。

Samples

5
1 2 3 4 5

0

5
1 3 2 4 5

3

Limitation

1s, 1024KiB for each test case.