Mountain Guard Placement

A mountain is represented as a polyline with n pavilions located at its vertices. The i-th pavilion is at point \((i, h_i)\). The area below the polyline is filled with rock. Nine can only play at these pavilions, and to keep her safe her father hires guards. A guard stationed at a pavilion q can only monitor pavilions with indices not exceeding q (to his left including his own position). However, due to technological limitations the guard can only see a pavilion p (with \(p < q\)) if the line segment connecting \((q, h_q)\) and \((p, h_p)\) does not pass through any rock. More precisely, if for any pavilion \(k\) with \(p < k < q\) the point \((k, h_k)\) lies below the line connecting \((q, h_q)\) and \((p, h_p)\), then the guard can see pavilion \(p\). Note that if the line exactly passes through any other pavilion (other than \(p\) and \(q\)), then pavilion \(p\) is not visible.

Now, considering that sometimes some pavilions might be out of service, the father wants to know, for every interval \([l, r]\) with \(1 \le l \le r \le n\), what is the minimum number of guards required so that every pavilion in the interval \([l, r]\) is monitored. In other words, only the pavilions from \(l\) to \(r\) (inclusive) may be used both to play and to station guards, and each pavilion in \([l, r]\) must be monitored by at least one guard.

A guard placed at pavilion \(q\) monitors a contiguous set of pavilions to his left: there exists an index \(L_q\) (\(1 \le L_q \le q\)) such that he can see every pavilion from \(L_q\) to \(q\) but cannot see pavilion \(L_q-1\) (if it exists). Given the mountain profile \(h_1, h_2, \dots, h_n\), the task is to answer several queries. Each query gives an interval \([l, r]\), and you must determine the minimum number of guards needed if only the pavilions in this interval can be used.

Visibility condition in LaTeX: A guard at pavilion \(q\) can see pavilion \(p\) (with \(p < q\)) if and only if for every \(k\) with \(p < k < q\), \[ h_k < h_p + \frac{h_q - h_p}{q - p}(k-p) \quad (\text{strict inequality}). \]

inputFormat

The first line contains an integer n indicating the number of pavilions. The second line contains n space-separated integers \(h_1, h_2, \dots, h_n\) representing the heights of the pavilions. The third line contains an integer q representing the number of queries. Each of the next q lines contains two integers l and r (\(1 \le l \le r \le n\)), representing an interval of pavilions.

outputFormat

For each query, output a single integer on a separate line — the minimum number of guards required to monitor all pavilions in the interval \([l, r]\).

sample

4
5 1 4 3
3
1 4
2 4
3 4

2
1
1