Description

知行楼四楼安装了很多灯，一天，Mr C看到了灯后，灵机一动，想要以此给大家出套题目，我们把开着的灯看作数字1，把关着的灯看作数字0，定义0 magic 0 = 1,0 magic 1 = 0,1 magic 1 = 1, 1 magic 0 = 0。现在Mr C有N 个问题query(l,r)，表示询问从左往右的第l 个灯向右一个一个magic到第r 个灯的结果是什么。

Format

Input

第1 行一个整数N 表示序列的长度。
第2 行N 个整数Ai，每个数不是0 就是1，表示灯是关的还是开的。
第3 行一个整数M 表示询问的个数。
第4~M+3 行，每行两个整数l 和r，表示询问magic(l,r)。

Output

共M 行，第i 行回答第i 个询问。

Sample 1

Input

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

Output

0
0
0
0
1

Limitation

1s, 128MB for each test case.

Hint

对于20%的数据，N和M <= 1000
对于30%的数据，N和M <= 5000
对于80%的数据，N和M <= 500000
对于100%的数据，N和M <= 1000000

Source

高一年级信息学奥赛模拟考(三)