Sign on Fence

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem

Panel $i$ has height $h_i$. For query $l,r,w$, choose exactly $w$ consecutive panels inside $[l,r]$. A rectangular sign can be as high as the minimum panel in that chosen block. Maximize this height.

Input

The first line contains $n$, then the heights, then $m$, followed by $m$ queries $l,r,w$.

Output

Print the maximum possible sign height for every query.

Subtasks

Subtask 1 (20%)

• $n\le 30$, number of queries $\le 30$.
• All other conditions are the same as Subtask 3.

Subtask 2 (30%)

• $n\le 3000$, number of queries $\le 3000$.
• All other conditions are the same as Subtask 3.

Subtask 3 (50%)

• $1\le n,m\le10^5$
• $1\le h_i\le10^9$
• $1\le l\le r\le n$
• $1\le w\le r-l+1$

Example

Input

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

Output

2
3
1

Explanation

For 2 5 3, panels 2..4 have heights [2,2,3], so a height-$2$ sign fits.