問題

1 から n までの番号が書かれた n 枚のカードがある．まず，一番上が番号 1 のカード，上から 2 枚目が番号 2 のカード，\ldots，一番下が番号 n のカードとなるように順番に重ねて，カードの山を作る．

カードの山に対して，「シャッフル (x, y) 」と呼ばれる次のような操作を行うことで，カードを並び替える（x, y は 1 \leqq x < y < n をみたす整数）．

シャッフル (x, y)

n 枚のカードを，一番上から x 枚目までのカードからなる山 A，x + 1 枚目から y 枚目のカードからなる山 B，y + 1 枚目から n 枚目のカードからなる山 C の 3 つの山に分ける．そして，山 A の上に山 B を重ね，さらにその上に山 C を重ねる．

例えば，順番に並んでいる 9 枚のカードに対して「シャッフル (3, 5)」を行うと，9 枚のカードに書かれた番号は，上から順番に 6, 7, 8, 9, 4, 5, 1, 2, 3 となる．

最初の山の状態から m 回のシャッフル「シャッフル (x_1, y_1)」「シャッフル (x_2, y_2)」\cdots「シャッフル (x_m, y_m)」を順番に行った後のカードの山において，上から数えて p 枚目から q 枚目のカードの中に番号が r 以下のカードが何枚含まれているかを求めるプログラムを作成せよ．

入力例 1

9
1
3 7 4
3 5

出力例 1

2

入力例 1 の山に対して, 「シャッフル (3, 5)」を行うと，カードは上から順番に 6, 7, 8, 9, 4, 5, 1, 2, 3 となる．上から数えて 3 枚目から 7 枚目に含まれる番号が 4 以下のカードは，番号 4 と番号 1 の 2 枚である．

入力例 2

12
3
3 8 5
3 8
2 5
6 10

出力例 2

3

入力例 2 の山に対して, 「シャッフル (3, 8)」「シャッフル (2, 5)」「シャッフル (6, 10)」を順番に行うと，カードは上から順番に 9, 10, 3, 11, 12, 4, 5, 6, 7, 8, 1, 2 となる．上から数えて 3 枚目から 8 枚目に含まれる番号が 5 以下のカードは 3 枚である．