P16330 Just Because!

> 瑛太把刚才拍的樱花树的照片发了上去。写到“大学很普通”。 > > ——看起来就是这样的感觉啊。这是来自她的回答，很疑惑，“看什么”，这到底是怎么回事。 > > 然后 line 画面上发来一张照片。像是在哪里见过的景色，在散落了一半的樱花树下有一个驼背男大学生的后背。瑛太的背包，瑛太的衣服，照片里的是瑛太本人。 > >怀着惊讶和确信的心情，慢慢地回头看。她在后面，十步左右的距离，恶作剧似地笑着。 > > “我并不是为了追求泉来这的，是因为这里的教育系比较有名。” > 她开心地告诉了我不知道的事情，有很多想说的话。 > >我有很多想说的话，想听的事情也很多。但在她面前，瑛太想要传达的就只剩下，那天没有说出口的话，那天最想传达的想法... > > “夏目，我喜欢你。” > > 在林荫大道上刮起大风，稍强的风把樱花吹得飘落下来，落在两人身上。 > > “我也是，泉。” > > 在樱吹雪的风中，她害羞地笑了起来。

You are given $n$ trees. The $i$-th tree is located at position $p_i$ and has height $h_i$. It is guaranteed that the sequence $p$ is strictly increasing. There are $q$ queries. For the $i$-th query, only the subarray $[l_i, r_i]$ is kept. You need to choose as many trees as possible such that there exists a way to cut them down so that no tree trunk hits another trunk. Formally, let $S=\{s_1,s_2,\dots,s_k\}\subseteq\{l_i,l_i+1,\dots,r_i\}$ with $s_1

The first line contains two positive integers $n,q$. The second line contains $n$ positive integers, denoting $h_i$. The third line contains a strictly increasing sequence of $n$ positive integers $p_i$. The next $q$ lines each contain two positive integers $l_i,r_i$, describing the query interval.

Output $q$ lines. Each line should contain one integer, the answer for the corresponding query.

**Constraints** For all test cases, $1\le n,q\le 5\times 10^5$, $1\le p_i,h_i\le 10^9$, and $l_i\le r_i$. For all $1\le i