#P4769. 超级贞鱼

超级贞鱼

超级贞鱼

题目描述

马达加斯加贞鱼有两只脚,每只脚上都写着一个数。初始时,kk 只贞鱼从左到右排成一列。第 ii 只的左脚上写 ii,右脚上写 aia_i。

每过一年,所有贞鱼按右脚上的数从小到大重新排列。若右脚上的数相同,保持它们原来的相对顺序。重新排列后,对于从左到右的第 ii 只贞鱼,先把它左脚上原来写的数记到右脚上,再把左脚上的数改成 ii。

经过 nn 年后,若第 ii 只贞鱼在第 jj 只的左边,且第 ii 只右脚上的数严格大于第 jj 只右脚上的数,则这两只贞鱼称为一对超级贞鱼。请计算这样的对数。

输入格式

第一行一个正整数 kk。

第二行 kk 个整数 a1,a2,…,aka_1,a_2,\ldots,a_k,表示初始队列中每只贞鱼右脚上的数。

第三行一个非负整数 nn,表示经过的年数。n=0n=0 时使用初始队列。

输出格式

输出一行一个整数,表示超级贞鱼对数。

样例 #1

样例输入 #1

6
5 2 6 3 1 7
0

样例输出 #1

7

数据范围

1≤ai≤1091\le a_i\le10^9,1≤k≤5×1061\le k\le5\times10^6,0≤n≤50000\le n\le5000。

题目来源

winmt,benny 命题。