Это простая версия задачи. В этой версии \(n \leq 5000\). Вы можете совершать взломы только в том случае, если решены обе версии задачи.
Орангутаны — могущественные существа — настолько могущественные, что им нужна всего \(1\) единица времени, чтобы уничтожить все уязвимые планеты во Вселенной!
Во Вселенной существует \(n\) планет. Каждая планета имеет интервал уязвимости \([l, r]\), в течение которого она будет подвержена разрушению орангутанами. Орангутаны также могут расширять интервал уязвимости любой планеты на \(1\) единицу.
В частности, предположим, что расширение происходит на планете \(p\) с интервалом уязвимости \([l_p, r_p]\). Тогда результирующий интервал уязвимости может быть либо \([l_p - 1, r_p]\), либо \([l_p, r_p + 1]\).
При заданном множестве планет орангутаны могут уничтожить все планеты, если интервалы уязвимости всех планет из множества пересекаются хотя бы в одной общей точке. Назовём счётом такого набора минимальное количество расширений, которое необходимо выполнить.
Орангутанов интересует сумма счётов всех непустых подмножеств планет во Вселенной. Поскольку ответ может быть очень большим, выведите его по модулю \(998\,244\,353\).
Выходные данные
Для каждого набора входных данных выведите целое число — сумму счётов всех непустых подмножеств планет во Вселенной, по модулю \(998\,244\,353\).
Примечание
В первом наборе входных данных есть семь непустых подмножеств планет, которые мы должны рассмотреть:
- Для каждого из подмножеств \(\{[1,1]\}, \{[2,3]\}, \{[3,3]\}\), оценка равна \(0\).
- Для подмножества \(\{[2,3], [3,3]\}\) оценка равна \(0\), потому что точка \(3\) уже содержится в интервале уязвимости обеих планет.
- Для подмножества \(\{[1,1], [2,3]\}\) оценка равна \(1\). Используя одну операцию по изменению интервала уязвимости второй планеты на \([1,3]\), обе планеты теперь имеют точку \(1\) в своем интервале.
- Для подмножества \(\{[1,1], [3,3]\}\) оценка равна \(2\). С помощью двух операций по изменению интервала уязвимости первой планеты на \([1,3]\), обе планеты теперь имеют точку \(3\) в своем интервале.
- Для подмножества \(\{[1,1], [2,3], [3,3]\}\) оценка равна \(2\). С помощью одной операции по изменению интервала уязвимости первой планеты на \([1,2]\) и одной операции по изменению интервала уязвимости третьей планеты на \([2,3]\), все три планеты будут иметь точку \(2\) в своем интервале.
Сумма оценок всех непустых подмножеств первого набора входных данных равна \(0 \cdot 4 + 1 \cdot 1 + 2\cdot2 = 5\).