Олимпиадный тренинг

Задача . A. Минимумы и максимумы


Массив называется красивым, если выполняются следующие два условия:

  • есть не меньше \(l_1\) и не больше \(r_1\) элементов в массиве, равных его минимуму;
  • есть не меньше \(l_2\) и не больше \(r_2\) элементов в массиве, равных его максимуму.

Например, в массиве \([2, 3, 2, 4, 4, 3, 2]\) \(3\) элемента, равные его минимуму (\(1\)-й, \(3\)-й и \(7\)-й), и \(2\) элемента, равные его максимуму (\(4\)-й и \(5\)-й).

Другой пример: в массиве \([42, 42, 42]\) \(3\) элемента, равные его минимуму, и \(3\) элемента, равные его максимуму.

Ваша задача — найти наименьшее возможное количество элементов в красивом массиве.

Входные данные

В первой строке записано одно целое число \(t\) (\(1 \le t \le 5000\)) — количество наборов входных данных.

Каждый набор состоит из одной строки, содержащей четыре целых числа \(l_1\), \(r_1\), \(l_2\) и \(r_2\) (\(1 \le l_1 \le r_1 \le 50\); \(1 \le l_2 \le r_2 \le 50\)).

Выходные данные

На каждый набор входных данных выведите одно целое число — наименьшее возможное количество элементов в красивом массиве.

Примечание

Оптимальные массивы в примере:

  1. \([1, 1, 1, 1]\), в нем \(4\) минимума и \(4\) максимума;
  2. \([4, 4, 4, 4, 4]\), в нем \(5\) минимумов и \(5\) максимумов;
  3. \([1, 2, 1, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2]\), в нем \(3\) минимума и \(10\) максимумов;
  4. \([8, 8, 8]\), в нем \(3\) минимума и \(3\) максимума;
  5. \([4, 6, 6]\), в нем \(1\) минимум и \(2\) максимума;
  6. \([3, 4, 3]\), в нем \(2\) минимума и \(1\) максимум;
  7. \([5, 5, 5, 5, 5, 5]\), в нем \(6\) минимумов и \(6\) максимумов.

Примеры
Входные данныеВыходные данные
1 7
3 5 4 6
5 8 5 5
3 3 10 12
1 5 3 3
1 1 2 2
2 2 1 1
6 6 6 6
4
5
13
3
3
3
6

time 2000 ms
memory 512 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя