더 빠른 정렬

올해부터 ACM-ICPC 월드 파이널에서 파이썬을 쓸 수 있다. 그 기념으로 파이썬에 관한 재미있는 사실 하나를 소개한다.

파이썬은 팀소트라는 정렬 알고리즘을 쓴다. 이미 순서가 맞는 부분배열로 배열을 나누고, 각 부분배열을 삽입정렬한 다음, 정렬된 부분배열을 합치는 방식이다. 그래서 순서대로 놓인 원소가 길게 이어질수록 정렬이 빨라진다.

이 문제는 배열을 부분배열로 나누는 과정만 다룬다. 현재 위치를 $i$라 하고, 배열이 끝날 때까지 다음 두 단계를 반복한다.

1. 위치 $i$에서 시작해 증가하거나 유지되는($a_i \le a_{i+1} \le a_{i+2} \le \cdots$) 부분배열과 감소하는($a_i > a_{i+1} > a_{i+2} > \cdots$) 부분배열을 각각 가능한 한 길게 잡고, 둘 중 더 긴 쪽을 고른다.
2. 부분배열의 길이가 $MINRUN$보다 작으면 뒤에 있는 원소를 하나씩 더 가져와 길이를 $MINRUN$으로 맞춘다. 이때 가져온 원소를 나쁜 원소라고 부른다. 길이를 맞추기 전에 배열이 끝나면 거기서 멈춘다.

다음 위치는 방금 만든 부분배열의 바로 뒤이다.

$MINRUN$이 작으면 합쳐야 할 부분배열이 많아지고, $MINRUN$이 크면 나쁜 원소가 많아져 삽입정렬이 힘들어진다. 그래서 적당한 $MINRUN$을 잡는 것이 중요하다. 부분배열을 합치는 과정 때문에 $N/MINRUN$이 2의 거듭제곱에 가까우면 좋다는 조건도 있지만, 이 문제에서는 고려하지 않는다.

$MINRUN$ 값이 주어질 때마다 부분배열의 개수와 나쁜 원소의 개수를 구하라.

첫째 줄에 배열의 길이 $N$이 주어진다. ($5 \le N \le 100\,000$)

둘째 줄에 배열의 원소 $N$개가 주어진다. 각 원소의 절댓값은 $10^9$ 이하이다.

셋째 줄에 쿼리의 개수 $Q$가 주어진다. ($1 \le Q \le 100\,000$)

넷째 줄부터 $Q$개의 줄에 걸쳐 $MINRUN$ 값이 한 줄에 하나씩 주어진다. ($2 \le MINRUN \le N$)

각 쿼리마다 부분배열의 개수와 나쁜 원소의 개수를 공백으로 구분해 한 줄에 출력한다.