You are given a permutation p1,p2,...,pn of numbers from 1 to n.

A permutation is a sequence of integers from 1 to n of length n containing each number exactly once. For example, [1] ,[4,3,5,1,2], [3,2,1] — are permutations, and [1,1], [4,3,1], [2,3,4] are not permutations.

You are given q queries where each query consists of two integers a and b, In response to each query you need to return number of inversions of permutation  after swapping elements at index a and b, Here every query is independent i.e. after each query the premutation is restored to its initial state.

An inversion in a permutation p is a pair of indices (i, j) such that i > j and p_i < p_j. For example, a permutation [4, 1, 3, 2] contains 4 inversions: (2, 1), (3, 1), (4, 1), (4, 3).

Input format

• The first line contains n,q.
• The second line contains the space-separated permutation p1,p2,...,pn.
• Each line of next q lines contain of two integers a,b . 

Output format

For each query Print an integer denoting the number of Inversion on new line.

Constraints

$2<=n<=100$

$1<=q<=10000$