k개의 부분 배열과 쿼리

시간 제한1초메모리 제한1024 MB

요약

각 부분 배열 A[l..r]마다 k개의 조각으로 잘라 순서를 바꿔 정렬할 수 있는 최소 k를 구한다.

난이도: 보통10점 중 7점
유형: 세그먼트 트리, 배열, 정렬
정답자: 아직 제출이 없습니다

문제

nlog는 다음과 같은 문제를 만들었다.

$N$ 개의 서로 다른 정수를 가진 배열 $A$ 가 주어진다. 당신은 공격력이 양의 정수 $k$ 인 칼을 받았다. 이 칼이 있으면 배열에 아래와 같은 연산을 적용할 수 있다.

배열을 $k$ 개의 조각으로 자른다.

$k$ 개의 조각을 원하는 순서대로 재배열한다.

재배열한 순서대로 조각들을 다시 합친다.

당신은 배열 $A$ 에 이 연산을 원하는 횟수만큼 적용하여 (한 번도 적용하지 않아도 괜찮다) 오름차순으로 정렬하려고 한다. $k$ 의 값에 따라 이 연산을 적절히 적용하면 $A$ 를 정렬하는 것이 가능할 수도 있고, 연산을 어떻게 잘 적용해도 정렬할 수 있는 방법이 없을 수도 있다. 이 때, 배열 $A$ 를 정렬할 수 있는 가장 작은 양의 정수 $k$ 의 값을 구하는 프로그램을 작성하자.

하지만, 문제가 너무 쉬워 보여 질의를 주기로 했다.

$l, r$ 이 주어지면 $A\_l, A\_{l + 1}, \cdots , A\_r$ 로 구성된 연속 부분 배열에서 문제의 정답을 출력하자.

입력

첫째 줄에 배열의 길이 $N$ 이 주어진다.

둘째 줄에 $N$ 개의 정수 $A\_1, A\_2, \cdots , A\_n$ 이 공백으로 구분되어 주어진다.

셋째 줄에 질의의 개수 $Q$ 가 주어진다.

넷째 줄부터 $Q$ 개의 줄에 질의의 정보 $l$ 과 $r$ 이 공백으로 구분되어 주어진다.

출력

각 질의마다 주어진 수열을 오름차순으로 만들 수 있는 가장 작은 양의 정수 $k$ 의 값을 출력한다.

제한

$1 \leq N \leq 200\\,000$
$1 \leq A\_i \leq 200\\,000$
$i \neq j$ 이면 $A\_i \neq A\_j$ , 즉 배열 $A$ 의 값들은 모두 서로 다르다.
$1 \leq Q \leq 200\\,000$
$1 \leq l \leq r \leq N$

예제3

예제 1
입력
```
5
1 2 3 4 5
2
1 1
1 5
```
예상 출력
```
1
1
```
예제 2
입력
```
6
4 5 6 1 2 3
3
1 3
2 4
1 6
```
예상 출력
```
1
2
2
```
예제 3
입력
```
6
3 4 5 6 1 2
3
1 4
6 6
1 6
```
예상 출력
```
1
1
2
```