ASISTENT - Asistent

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

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

hide comments
2020-06-09 09:09:11
which algorithm is needed for this problem?
2016-03-08 23:03:13 Scape
Time limit is indeed too strict. O(N log^2 N) times out...
2011-09-15 02:07:18 applepi
Time Limit may be too strict T_T
2010-07-30 22:53:02 Vladimir Kirichenkoff
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.
2010-11-07 13:53:53 Ivan Katanic
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.
2010-06-27 11:47:05 Lox
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
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.