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$。