세 대의 기계

Spaceman Spoof's Functions에서 Abhilash, Brian, 그리고 당신 Spaceman Spoof는 사악한 Zargon으로부터 탈출할 수 있었다. 하지만 그들의 팀의 네 번째 멤버인 Aditya가 들어갈 자리가 없어 위험한 상황에 놓였다. 그는 Zargon 감옥에 갇혀 있으며, 세 대의 이상한 기계와 아무것도 쓰이지 않은 카드 한 장을 가지고 있다. 방을 나가려면 $n$개의 잠긴 문을 통과해야 하며, 각 문은 특정한 두 수의 쌍이 적힌 카드가 있어야 열린다. Aditya는 자신의 카드에 정수 쌍 $(a,b)$를 적을 수 있으며, 이때 양의 정수 $m$에 대해 $1 \leq a < b \leq m$을 만족해야 한다. 그런 다음 그는 감방에 있는 세 대의 기계를 사용할 수 있는데, 각 기계는 카드 한 장 또는 두 장을 받아 새 카드를 출력하며, 입력으로 넣은 원래 카드들은 모두 돌려받는다:

1. 첫 번째 기계는 $(x,y)$가 적힌 카드를 받아 $(x + 1, y + 1)$이 적힌 카드를 출력한다.
2. 두 번째 기계는 $(x,y)$가 적힌 카드를 받아 $x$와 $y$가 모두 짝수이면 $(x/2, y/2)$가 적힌 카드를 출력한다. 그렇지 않으면 새 카드를 출력하지 않는다.
3. 마지막 기계는 $(x,y)$와 $(y,z)$가 적힌 두 카드를 받아 $(x, z)$가 적힌 카드를 출력한다.

Aditya에게는 시간이 무한히 많으므로 이 기계들을 필요한 만큼 사용할 수 있다. Zargon은 수다스러워서 Aditya는 간수들로부터 $i$번째 잠긴 문은 $(1, a_i)$가 적힌 카드로 열 수 있다는 것을 알아냈다. 정수 배열 $[a_1, a_2, \dots, a_n]$이 주어졌을 때, Aditya가 처음 카드에 적는 정수 쌍 $(a,b)$ 중 몇 개에 대해 Aditya가 결국 감옥을 탈출할 수 있는가?

입력의 첫 번째 줄에는 공백으로 구분된 두 정수 $n$과 $m$ $(1 \leq n \leq 10^5, 2 \leq m \leq 10^{15}$)이 주어지며, 각각 Aditya의 감방을 지키는 잠긴 문의 수와 Aditya가 처음 카드에 적을 수 있는 최댓값이다.

다음 줄에는 $n$개의 공백으로 구분된 정수 $a_1$부터 $a_n$까지가 주어지며, $2 \leq a_i \leq 10^{15}$이다. Aditya는 $i$번째 문을 열기 위해 $(1,a_i)$가 적힌 카드를 만들어야 한다. ($a_i$는 서로 다를 필요가 없다.)

$1\leq a < b \leq m$인 시작 카드 $(a,b)$ 중 Aditya가 탈출에 필요한 모든 카드를 만들 수 있는 것의 개수를 출력한다. 답은 C++ long long에 들어감이 보장된다.