Տեսակավորման ալգորիթմ
Դավիթն ուսումնասիրում է տեսակավորման ալգորիթմները։ Նա արդեն յուրացրել է մի քանի ալգորիթմ, այդ թվում պղպջակի ալգորիթմը։ Այժմ նա հետազոտում է մի ալգորիթմ, որտեղ թույլատրվում է հաջորդականության ցանկացած տարր հանել իր տեղից և տեղափոխել վերջը։
Օգնեք Դավիթին պարզելու տրված հաջորդականությունը նշված գործողությունով տեսակավորելու համար մինիմալ քայլերի քանակը։
Մուտքային տվյալներ
Առաջին տողում տրված է տարրերի
N (1 < N ≤ 500 000) քանակը։ Երկրորդ տողում տրված է N երկարության ամբողջ թվերի հաջորդականությունը։ Հաջորդականության տարրերն իրարից անջատված են մեկական բացատով։Ելքային տվյալներ
Պետք է արտածել մեկ թիվ՝ նշված եղանակով տեսակավորումն անելու համար մինիմալ քայլերի քանակը։
Օրինակ
Մուտք | Ելք |
6
11 13 15 12 14 16 | 4 |
Աղբյուրը. Մարզային 2018
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB