有一座圓形停車塔，其中 $N$ 個車位圍成一圈。按順時針方向依序稱為第 1、第 2、……、第 $N$ 個車位。每個車位都有一輛車。第 $i$ 個車位中的車的編號為 $a_i$。

停車塔有兩個按鈕。按下按鈕 A 可使停車塔順時針旋轉一個車位，按下按鈕 B 則使其逆時針旋轉一個車位。下方左圖表示上例按下 A 後的狀態，右圖表示按下 B 後的狀態。

現在要將停車塔中的所有車取出。

只能從最下方的一個車位取車。初始時第 1 個車位位於最下方。要取出其他車位中的車，必須先適當按動按鈕旋轉停車塔，使該車所在車位移到最下方。

此外，要取出編號為 $x$ 的車，必須先取出所有編號小於 $x$ 的車。也就是說，只要塔內還剩下編號小於 $x$ 的車，就不能取出編號為 $x$ 的車。

請編寫程式，求出取出所有車所需按動按鈕的最少總次數。

資料範圍

• $1 \le N \le 100\,000$
• $1 \le a_i \le 1\,000\,000\,000$

子任務

1.（8 分）$a_i=1$（$1\le i\le N$），即所有車的編號均為 1。 2.（9 分）當 $i\ne j$ 時有 $a_i\ne a_j$，即所有車的編號互不相同。 3.（10 分）$N\le10$。 4.（21 分）$N\le100$。 5.（31 分）$N\le1\,000$。 6.（21 分）沒有額外限制。

輸入格式

第一行給出整數 $N$。

第二行按順序給出車的編號 $a_1,\ldots,a_N$，用空格分隔。

輸出格式

在第一行輸出按動按鈕的最少總次數。

範例

輸入格式 1

4
1 2 2 1

輸出格式 1

3

說明

可以按以下順序操作：取車 → 按鈕 A → 取車 → 按鈕 A → 取車 → 按鈕 A → 取車。

輸入格式 2

5
3 1 4 5 1

輸出格式 2

7