Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem F: 五队-长春-数江老板

Problem F: 五队-长春-数江老板

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 84  Solved: 15
[Submit][Status][Web Board]

Description

在未来克隆技术越来越成熟,朱大神发现只有两个队友太少了,那就克隆一窝吧(foreverNo.1,foreverNo.2,…,foreverNo.n),但是克隆机器必须要朱大神控制,于是他请了after来帮忙观察克隆情况,after表示没睡醒于是就每次从克隆结果中随便找一个告诉朱大神。腹黑的朱大神马上就发现了after的消极怠工,于是故意在after数完后连问m次第i次数到第j次数之间有几种foreverNo.(问题可能重复但是一定满足i≤j,同时0<i,j≤n),after很快解决了这个问题,聪明的你能解决吗?

Input

第一行包含一个一个正整数n (1 ≤ n ≤ 30000).,第二行有n个字符串,第三行只有一个正整数m (1 ≤ m ≤ 200000),接下来m行每行包含两个正整数i、j (i≤j,同时0<i,j≤n)

Output

对于每个问题输出有几种foreverNo.。

Sample Input

5
foreverNo.1 foreverNo.1 foreverNo.2 foreverNo.1 foreverNo.3
3
1 5
2 4
3 5

Sample Output

3
2
3

HINT

[Submit][Status][Web Board]