Bartek 是一位著名的電子音樂（techno）製作人，目前他正在完善他的下一首熱門單曲。他創作了一首由 $n$ 個節拍組成的曲目，編號依序為 $1$ 到 $n$。在音樂編輯程式中花費了數小時後，他正準備匯出 mp3 檔案，卻發現這些節拍目前的排列順序為 $a_1, a_2, \dots, a_n$。Bartek 需要將節拍排列成遞增順序，亦即 $1, 2, \dots, n$。

該程式允許兩種操作：

• 將最後一個節拍移動到任意位置，例如 $(2, 4, 1, 5, \underline{3}) \to (2, \underline{3}, 4, 1, 5)$。
• 將任意一個節拍移動到最開頭，例如 $(2, 4, 1, \underline{5}, 3) \to (\underline{5}, 2, 4, 1, 3)$。

要將節拍按遞增順序排列，最少需要多少次操作？

輸入格式

第一行包含一個整數 $n$ ($1 \le n \le 200\,000$)，代表節拍的數量。

第二行包含 $n$ 個兩兩相異的整數 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n; a_i \ne a_j$)，代表程式中節拍目前的順序。

輸出格式

輸出一個整數 —— 所需的最少操作次數。

範例

輸入 1

6
3 2 5 4 1 6

輸出 1

4

輸入 2

9
3 1 2 5 6 4 9 7 8

輸出 2

6

說明

我們從節拍序列 $(3, 2, 5, 4, 1, 6)$ 開始。以下是透過四次操作達成目標順序的一種方式：

• 將最後一個節拍向左移動兩個位置：$(3, 2, 5, \underline{6}, 4, 1)$。
• 將節拍 $2$ 移動到最開頭：$(\underline{2}, 3, 5, 6, 4, 1)$。
• 將節拍 $1$ 移動到最開頭：$(\underline{1}, 2, 3, 5, 6, 4)$。
• 將最後一個節拍向左移動兩個位置：$(1, 2, 3, \underline{4}, 5, 6)$。

也可以透過其他方式使用四次操作獲得遞增順序，但無法在三次操作內完成，因此結果為 $4$。