Вам задан массив, состоящий из \(n\) чисел \(a_1\), \(a_2\), ..., \(a_n\). Изначально \(a_x = 1\), а остальные элементы равны \(0\).
Вы выполняете \(m\) операций. Во время \(i\)-й операции вы выбираете два индекса \(c\) и \(d\) таких, что \(l_i \le c, d \le r_i\), и меняете местами \(a_c\) и \(a_d\).
Посчитайте количество индексов \(k\) таких, что существуют возможность выбрать операции так, что в конце \(a_k = 1\).
Выходные данные
На каждый набор входных данных выведите одно число — количество индексов \(k\) таких, что существуют возможность выбрать операции так, что в конце \(a_k = 1\).
Примечание
В первом наборе входных данных условие \(a_k = 1\) выполняется для любого \(k\). Для этого, можно выполнить следующие операции:
- поменять местами \(a_k\) и \(a_4\);
- поменять местами \(a_2\) и \(a_2\);
- поменять местами \(a_5\) и \(a_5\).
Во втором наборе входных данных подходят только индексы \(k = 1\) и \(k = 2\). Для выполнения \(a_1 = 1\), нужно поменять местами \(a_1\) и \(a_1\) во второй операции. Для выполнения \(a_2 = 1\), нужно поменять местами \(a_1\) и \(a_2\) во второй операции.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
6 4 3
1 6
2 3
5 5
4 1 2
2 4
1 2
3 3 2
2 3
1 2
|
6
2
3
|