小A有一个长度为n的排列， 小A想要知道这个排列中，所有区间的中位数。 不过最近小A沉迷巫师3，到处打牌无法自拔，所以他找到了你，希望你能够解决这个问题。 设区间l,r的中位数为 为了方便，只需要你输出。 答案对取模。 中位数的定义： 对于一个不重集合，将这个集合里的数从小到大排序为 当m是奇数，S的中位数为 当m是偶数，S的中位数为

输入描述:

第一行两个正整数n,seed ,含义如题目所示第二行一个排列p

输出描述:

一个正整数ans。