문제

부터 까지의 수가 한 번씩 등장하는 크기 의 순열 (1-index)가 주어진다.

베개는 이 순열을 세상에서 가장 효율적인 정렬 알고리즘으로 정렬하고자 한다. 다음 쿼리를 처리하는 프로그램을 작성하시오.

• i j: 범위 에 해당하는 부분 순열 를 버블 정렬할 때 필요한 최소 인접 교환 횟수를 구해서 출력한다.

인접 교환은 인 정수 를 정해, 와 의 값을 서로 교환하는 연산이다.

버블 정렬은 인접 교환으로만 순열을 오름차순으로 정렬하는 알고리즘이다. 예를 들어, 을 버블 정렬하기 위해 필요한 인접 교환 횟수는 2회이다.

입력

첫 번째 줄에 두 정수 과 가 주어진다.

두 번째 줄에 순열 의 각 원소가 공백으로 구분되어 주어진다. 는 부터 까지의 수가 한 번씩 등장하는 순열이다.

세 번째 줄부터 개의 줄에 걸쳐, 각 줄마다 쿼리 가 주어진다.

출력

각 쿼리에 대해, 한 줄에 하나씩 쿼리의 정답을 출력한다.