Library Irritation

At Galliston University, the Imperial Library faces a challenging book arrangement problem. XiaoDou, the librarian, must arrange books in increasing order of page numbers. However, when two books are out of order (i.e. if a book with a higher number of pages appears to the left of a book with a lower number of pages), his irritation increases by the sum of the page counts of the two books. Formally, if the books are arranged in an order given by an array pages[1..n], then the irritation is defined as:

[ \text{Irritation} = \sum_{1 \le i < j \le n ; \text{and} ; pages[i] > pages[j]} ; (pages[i] + pages[j]) ]

Initially, there are n books in a given order. Over the next m days, the order will change due to reader activities. On each day a swap occurs between two books at specified positions (1-indexed). XiaoDou is required to sort the books on at least one day within these m days. To decide the best day (with minimum irritation), he wants to know the irritation level on day i if he does not tidy up during the first i days and sorts the books on the i-th day. Your task is to compute and output the irritation level after each day's swap operation.

inputFormat

The input begins with a line containing two integers $n$ and $m$, where $n$ is the number of books and $m$ is the number of days. The second line contains $n$ integers, representing the number of pages in each book. Each of the following $m$ lines contains two integers $a$ and $b$ (1-indexed), indicating that on that day the books at positions $a$ and $b$ are swapped.

outputFormat

Output $m$ lines. The $i$-th line should contain a single integer representing the irritation level on day $i$ (i.e. after performing the swap on day $i$).

sample

3 2
3 1 2
1 2
2 3

5
0