ASISTENT - Asistent

no tags 

You are given a permutation of first N natural numbers on which you are to perform K operations of following type: given integers A and B, your task is to swap elements on positions A and B in permutation and then output permutation rank modulo 1000 000 007.

Note: Difference from original task is that elements remain swapped after query.

Input

On first line of standard input you are given two integers (2 ≤ N ≤ 50 000, 1 ≤ K ≤ 30 000), length of permutation and number of operations.
On the next line there is permutation of first N natural numbers.
In next K lines there are two integers A, B ( 1 ≤ A, B ≤ N ).

Output

Output permutation rank after applying each of K operations.

Example

Input:
5 3
1 5 4 2 3
1 3
2 3
2 5

Output:
91
77
90

hide comments
Scape: 2016-03-08 23:03:13

Time limit is indeed too strict. O(N log^2 N) times out...

applepi: 2011-09-15 02:07:18

Time Limit may be too strict T_T

Vladimir Kirichenkoff: 2010-07-30 22:53:02

it's a number of the permutation. For example, rank 123 - 1, rank 132 - 2, rank 213 - 3, rank 231 - 4, rank 312 - 5, rank 321 = 6.

Ivan Katanic: 2010-11-07 13:53:53

Yes, but you probably have big constant factor. Your solution times out on 6th case and it would fail even if time limit is 10 s, so far accepted solutions passed even 10th test under 6-7 s.

Lox: 2010-06-27 11:47:05

Is an O(NlogN+K(logN)^2) approach expected to be accepted? I've got TLE. :S
Edit: Phew! I've got AC eventually with an O(NlogN+K(NlogN)^0.5) approach.

Last edit: 2010-06-29 05:28:49

Added by:Ivan Katanic
Date:2010-06-23
Time limit:1.585s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:Modified task from Croatian IOI Team Selection Test