TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P5945
  • Problem
  • P5945超级贞鱼
    Limits : Time Limit : - MS   Memory Limit : - KB
    Judgment Tips : 1s,128m
    Description

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

    Input Format

    一共3行,第一行一个正整数k(\(1≤k≤10^5\)),
    第二行k个数从左到右输入Ai( \(1≤Ai≤10^9\)),
    第三行一个正整数n( $1≤n≤10^5 $)。

    Output Format

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

    Sample Input

    6
    5 2 6 3 1 7
    0

    Sample Output

    7

    Hint

    对于全部数据:\(Ai≤10^9\)
    30%的数据:n,k<=400;
    70%的数据:n,k<=10000;
    100%的数据:n,k<=100000;
    \(k\le 2\times10^6, n\le 10^{18}\)