A calibration rig monitors n sensors that share one baseline reading array. All of the sensors are known to drift together: at any moment, sensor i's calibrated reading equals baseline[i] + d for one common integer offset d (which may be positive, negative, or zero) that is the same for every sensor at that moment. Each sensor also has its own admissible reading window [l_i, u_i]; a calibrated reading is valid for that sensor only if it falls inside its window, inclusive of both ends. Count how many integer offsets d make every sensor's calibrated reading fall inside its own window at the same time.

Input format

• Line 1: an integer n, the number of sensors.
• Line 2: n space-separated integers, the baseline readings baseline[0], ..., baseline[n-1].
• Each of the next n lines contains two integers l_i and u_i: the admissible window for sensor i (0-indexed, in the same order as the baseline readings).

Output format

Print a single integer: the number of valid integer offsets d (print 0 if none exist).

Constraints

• 2 <= n <= 100
• 1 <= baseline[i] <= 10^6 for every sensor
• 0 <= l_i <= u_i <= 10^6 for every sensor

3
3 7 9
1 5
5 9
7 11

5

2
10 10
0 5
20 25

0