3327 - 破解符文

破解了符文之语,小 FF 开启了通往地下的道路。当他走到最底层时,发现正前方有一扇巨石门,门上雕刻着一幅古代人进行某种活动的图案。而石门上方用古代文写着“神的殿堂”。小 FF 猜想里面应该就有王室的遗产了。但现在的问题是如何打开这扇门……。

仔细研究后,他发现门上的图案大概是说:古代人认为只有智者才是最容易接近神明的。而最聪明的人往往通过一种仪式选拔出来。仪式大概是指,即将隐退的智者为他的候选人写下一串无序的数字,并让他们进行一种操作,即交换序列中相邻的两个元素。而用最少的交换次数使原序列变成不下降序列的人即是下一任智者。

小 FF 发现门上同样有着n个数字。于是他认为打开这扇门的秘诀就是找到让这个序列变成不下降序列所需要的最小次数。但小 FF 不会……只好又找到了你,并答应事成之后与你三七分……

输入

第一行为一个整数n,表示序列长度。
第二行为n个整数,表示序列中每个元素。对于100%的数据1≤n≤5*10^5,A[i]∈[−2^31,2^31)。

输出

一个整数ans,即最少操作次数。

样例

输入

4
2 8 0 3

输出

3

提示

开始序列为2,8,0,3,目标序列为0, 2, 3, 8,可进行三次操作的目标序列:

  1. 交换 8,0,序列变成 2,0,8,3;
  2. 交换 2,0,序列变成 0,2,8,3;
  3. 交换 8,3,序列变成 0,2,3,8。
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题