Preparing NOJ

超级贞鱼

10000ms 65536K

Description:

马达加斯加贞鱼是一种神奇的双脚贞鱼,它们把自己的智慧写在脚上——每只贞鱼的左脚和右脚上各有一个数。有
一天,K只贞鱼兴致来潮,排成一列,从左到右第i只贞鱼会在右脚写Ai,左脚上写上i;第二年,这K只贞鱼以右脚
的数为第一关键字、左脚的数为第二关键字,从小到大排成一列。然后,它们决定重编号,从左到右第i只贞鱼会
在右脚上写上左脚的数,在左脚上写i;第三年,它们按第二年的方法重排列、重编号......N年后,对于从左到右
第i和第j贞鱼,若i<j且第i只贞鱼右脚上的数比第j只贞鱼右脚上的数大,则称它们为一对“超级贞鱼”。问一共
有多少对“超级贞鱼”?

Input:

共3行,第一行一个正整数K,表示有K只贞鱼。
第二行K个正整数,第i个数表示Ai。
第三行一个非负整数N,表示年数。
K≤2×10^6, Ai≤10^9,N≤10^18

Output:

一个整数,表示“超级贞鱼”的对数。

Sample Input:

6
5 2 6 3 1 7
0

Sample Output:

7

Note:

 2017.09.01更换数据并重测

Info

BZOJ

Provider BZOJ

Origin By winmt benny命题

Code BZOJ4769

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 08/25/2019 18:55:22

Related

Nothing Yet