문제
피아노를 사랑하는 시은이는 매일 아침 피아노 체조를 한다. 시은이는 _N_개의 악보를 가지고 있으며, 1번부터 _N_번까지의 번호로 부른다. 각 악보는 1 이상 109 이하의 정수로 표현되는 난이도를 가지고 있다. 난이도를 나타내는 수가 클수록 어려운 악보이다. 1 ≤ x ≤ y ≤ N 을 만족하는 두 정수 x, _y_를 골라 _x_번부터 _y_번까지의 악보를 번호 순서대로 연주하는 것이 피아노 체조이다.
시은이는 피아노 체조를 할 때, 지금 연주하는 악보가 바로 다음에 연주할 악보보다 어렵다면 실수를 한다. 다시 말하자면, i(x ≤ i < y)번 악보의 난이도가 i + 1번 악보의 난이도보다 높다면 실수를 한다. 특히, 마지막으로 연주하는 _y_번 악보에선 절대 실수하지 않는다. 시은이는 오늘도 피아노 체조를 하기 위해 두 정수 _x_와 _y_를 골랐고, 문득 궁금한 것이 생겼다. 오늘 할 피아노 체조에서 실수하는 곡은 몇 개나 될까?
입력
첫 번째 줄에 악보의 개수 N(1 ≤ N ≤ 100,000)이 주어진다.
두 번째 줄에 1번 악보부터 _N_번 악보까지의 난이도가 공백을 구분으로 주어진다.
세 번째 줄에 질문의 개수 Q(1 ≤ Q ≤ 100,000)이 주어진다.
다음 _Q_개의 줄에 각 줄마다 두 개의 정수 x, y(1 ≤ x ≤ y ≤ N)가 주어진다.
출력
_x_번부터 _y_번까지의 악보를 순서대로 연주할 때, 몇 개의 악보에서 실수하게 될지 0 이상의 정수 하나로 출력한다. 각 출력은 개행으로 구분한다.
예제 입력 1
9
1 2 3 3 4 1 10 8 1
5
1 3
2 5
4 7
9 9
5 9예제 출력 1
0
0
1
0
3예제 입력 2
6
573 33283 5572 346 906 567
5
5 6
1 3
2 2
1 6
3 6예제 출력 2
1
1
0
3
2노트
- 실수한 개수의 누적합을 구하는 방향으로 진행
- 마지막으로 연주하는 y번 악보에서는 절대 실수하지 않는다는 조건을 바탕으로 실수한 개수의 구간 합
(x...y)를 구할 때y-1번의 누적합과x-1번의 누적합 차를 구하면 될 것 같다.
#include <iostream>
#include <vector>
#define IO std::cin.tie(NULL), std::ios_base::sync_with_stdio(false)
#define MAX 100001
int N, Q;
void solve() {
std::cin >> N;
std::vector<int> sheet(N + 1, 0);
std::vector<int> prefix(N + 1, 0);
for (int i = 1; i <= N; i++) {
int x;
std::cin >> x;
sheet[i] = x;
bool miss = sheet[i] < sheet[i - 1];
prefix[i - 1] += miss;
prefix[i] = prefix[i - 1];
}
std::cin >> Q;
for (int i = 0; i < Q; i++) {
int x, y;
std::cin >> x >> y;
std::cout << prefix[y - 1] - prefix[x - 1] << '\n';
}
}
int main() {
IO;
solve();
return 0;
}