시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB311100.000%

문제

After being stuck at home for months because of covid, you decided to explore the contents of your parent’s basement. Among numerous useless items, you found one peculiar object - a sorting device from the sixties that was used to teach sorting algorithms. The device consists of N ordered slots that get initialized with distinct integers once the device is turned on, and a screen for tracking cost. As a user, you can perform swap operations. One swap operation allows you to swap elements at positions i and j for a total cost of A×|i−j|+B, where A, B are parameters written on the back of the device. Since you’ve been studying your sorting algorithms, you definitely know how to sort the numbers with the smallest possible cost. Right?

입력

The first line contains a single integer N (1 ≤ N ≤ 2 · 105) - the number of slots the machine has. The next line has N space-separated integers up to 109 in absolute value that the machine generated after you turned it on. The last line has two positive integers A, B from the machine specs. 1 ≤ A, B ≤ 1 000.

출력

In the first line, output the smallest cost needed to sort the sequence. In the second line, output K - the number of swaps needed to do that. In the next K lines output the description of the swaps that need to be done. In each line output two numbers - indices of elements to be swapped, separated by a space. Indices start with one. If two or more sequences have the same total cost, you can output any of them.

예제 입력 1

4
42 35 13 21
1 1

예제 출력 1

7
3
1 3
3 4
2 3

예제 입력 2

6
6 5 4 3 2 1
5 3

예제 출력 2

54
3
3 4
2 5
1 6