题目描述

给你一个序列$\red s$，你把这个序列的所有不同排列按字典序排列后，求$\red s$的排名$\red {\%m}$

输入格式

序列的长度$\red{n<300000,m ,n}$个数，代表序列$\red s$

输出格式

排名$\red {\%m}$

样例

输入样例

4 1000
2 1 10 2

输出样例

5

数据范围与提示

所有比给定的排列更小的排列（相对于字典顺序）是：($\red {1,2,2,10}$), ($\red {1,2,10,2}$), ($\red {1,10,2,2}$) 和 ($\red {2,1,2,10}$).

$\red{2<=m<=10^9,1<=S_i<=300000}$