Problem:


Score : 900 points

Problem Statement

You are developing frog-shaped robots, and decided to race them against each other.

First, you placed N robots onto a number line.
These robots are numbered 1 through N.
The current coordinate of robot i is x_i.
Here, all x_i are integers, and 0 < x_1 < x_2 < ... < x_N.

You will repeatedly perform the following operation:

Select a robot on the number line. Let the coordinate of the robot be x. Select the destination coordinate, either x-1 or x-2, that is not occupied by another robot. The robot now jumps to the selected coordinate.

When the coordinate of a robot becomes 0 or less, the robot is considered finished and will be removed from the number line immediately.
You will repeat the operation until all the robots finish the race.

Depending on your choice in the operation, the N robots can finish the race in different orders.
In how many different orders can the N robots finish the race?
Find the answer modulo 10^9+7.

Constraints

2 ≤ N ≤ 10^5

x_i is an integer.

0 < x_1 < x_2 < ... < x_N ≤ 10^9

Partial Score

In a test set worth 500 points, N ≤ 8.

Input

The input is given from Standard Input in the following format:

N
x_1 x_2 ... x_N

Output

Print the number of the different orders in which the N robots can finish the race, modulo 10^9+7.

Sample Input 1

3
1 2 3

Sample Output 1

4

There are four different orders in which the three robots can finish the race:

(Robot 1 → Robot 2 → Robot 3)

(Robot 1 → Robot 3 → Robot 2)

(Robot 2 → Robot 1 → Robot 3)

(Robot 2 → Robot 3 → Robot 1)

Sample Input 2

3
2 3 4

Sample Output 2

6

There are six different orders in which the three robots can finish the race:

(Robot 1 → Robot 2 → Robot 3)

(Robot 1 → Robot 3 → Robot 2)

(Robot 2 → Robot 1 → Robot 3)

(Robot 2 → Robot 3 → Robot 1)

(Robot 3 → Robot 1 → Robot 2)

(Robot 3 → Robot 2 → Robot 1)

For example, the order (Robot 3 → Robot 2 → Robot 1) can be achieved as shown in the figure below:

Sample Input 3

8
1 2 3 5 7 11 13 17

Sample Output 3

10080

Sample Input 4

13
4 6 8 9 10 12 14 15 16 18 20 21 22

Sample Output 4

311014372

Remember to print the answer modulo 10^9+7.
This case is not included in the test set for the partial score.



Sample input:
3
1 2 3


Sample output:
4

Submission status: Wrong Answer

Solution code:
N=int(input())
X=list(map(int,input().split()))
P=1
Y=[]
X=X[::-1]
for i in range(N):
  Y.append(i+1)
  if X[-(i+1)]<2*i+1 and len(Y)==i+1:
    P*=Y.pop()
mod=10**9+7
for i in range(1,len(Y)+1):
  P=P*i%mod
print(P)

Submission status: Wrong Answer

Solution code:
N=int(input())
X=list(map(int,input().split()))
P=1
Y=[]
for i in range(N):
  Y.append(i+1)
  if X[i]<2*i+1 and len(Y)==i+1:
    P*=Y.pop()
mod=10**9+7
for i in range(1,len(Y)+1):
  P=P*i%mod
print(P)

Submission status: Wrong Answer

Solution code:
import sys
# from collections import defaultdict, deque
# import math
# import copy
from bisect import bisect_left, bisect_right
# import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 1000000007
def solve():
    n = getN()
    nums = getList()
    kaijyo = [1, 1]

    for i in range(2, n + 3):
        kaijyo.append((kaijyo[-1] * i % MOD))

    ans = 1
    prev = -1
    sukima = 0
    cnt = 0
    for num in nums:
        sukima += num - prev - 1

        if sukima < cnt:
            ans *= kaijyo[cnt]
            ans %= MOD
            cnt -= 1
            sukima += 1
        cnt += 1
        prev = num
        # print(ans, cnt, sukima)
    ans *= kaijyo[cnt]
    ans %= MOD
    print(ans)

def main():
    n = getN()
    for _ in range(n):
        solve()
if __name__ == "__main__":
    # main()
    solve()

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
n = int(input())
X = list(map(int, input().split()))

ans = []
now_x = 0
now_num = 0
free = n
for k,x in enumerate(X):
  now_num += 1
  dist = x - now_x
  if dist // 2 + 1 < now_num:
    ans += [free] * (now_num-1)
    free -= 1
    now_num = 1
    now_x = x-1
ans += [free] * now_num
res = 1
res2 = 1
for k,v in enumerate(ans[::-1]):
  res *= v-k
  res %= mod
print(res)

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
n = int(input())
X = list(map(int, input().split()))

ans = []
now_x = 0
now_num = 0
free = n
for k,x in enumerate(X):
  now_num += 1
  dist = x - now_x
  if dist // 2 + 1 < now_num:
    ans += [free] * (now_num-1)
    free -= 1
    now_num = 1
    now_x = x-1
ans += [free] * now_num
res = 1
res2 = 1
print(ans)
for k,v in enumerate(ans[::-1]):
  print(v-k)
  res *= v-k
  res %= mod
print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = [int(x) for x in input().split()]
p = 10 ** 9 + 7
P = [1 for _ in range(N + 1)]
for i in range(N):
  P[i + 1] = P[i] * (i + 1) % p
T = [N - 1] * N
pos = 0
for i in range(N):
  if 2 * i + 1 - X[i] >= 2 * pos + 1:
    T[pos] = i
    pos += i
cnt = 1
for i, t in enumerate(T):
  cnt *= t + 1 - i
  cnt %= p
print(cnt)

Submission status: Wrong Answer

Solution code:
print("sdf")

Submission status: Wrong Answer

Solution code:
input()
a=b=1
for r in input().split():
    a*=b%(10**9+7)
    if b*2<eval(r+'+2'):b+=1
print(a)

Submission status: Wrong Answer

Solution code:
input()
a=b=1
for r in input().split():
    a*=b%(10**+7)
    if b*2<eval(r+'+2'):b+=1
print(a)

Submission status: Wrong Answer

Solution code:
M = 10**9+7


def solve(n, x):
    p = 1
    for i in range(n):
        if p < x[i]:
            x[i] = p
            p += 2
        else:
            p = x[i] + 2
    # print('x:', x)
    b = 1
    t = []
    for i in range(1, n):
        if x[i-1] + 1 == x[i]:
            b += 1
        else:
            t.append(b)
            b = 1
    t.append(b)
    # print('t:', t)
    res = 1
    i = n
    for u in t:
        y = u
        while y >= 1:
            if y == 1:
                res *= i
                res %= M
                i -= 1
                y -= 1
            else:
                res *= 2
                res *= i - 1
                res %= M
                i -= 2
                y -= 2
    return res




n = int(input())
x = list(map(int, input().split()))
print(solve(n,x))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*- #

import math


def countSpace(coorsList, Nnum):
    spaces = coorsList[0] - 1
    for frog in range(1, Nnum):
        if not (coorsList[frog] - coorsList[frog-1] == 1):
            spaces += 1
    return spaces


def countPlace(coorsList, frog):
    if 2 + countSpace(coorsList, frog) - (frog + 1) >= 0:
        return 1
    return 1 - (2 + countSpace(coorsList, frog) - (frog + 1))

Nnum = long(raw_input())
coors = raw_input()
coorsStrList = coors.split()
coorsList = []
for c in coorsStrList:
    coorsList.append(long(c))


# coorsList.reverse()
result = 1
placeCounter = 0
tmpFrogCounter = Nnum
for n in range(Nnum):
    for frog in reversed(range(tmpFrogCounter)):
        if countPlace(coorsList, frog) == 1:
            result *= math.factorial(frog+1)
            coorsList.remove(coorsList[0])
            tmpFrogCounter -= 1
            break
    if frog == tmpFrogCounter:
        break

print result%((10**9)+7)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*- #

import math


def countSpace(coorsList, Nnum):
    spaces = coorsList[0] - 1
    for frog in range(1, Nnum):
        spaces += coorsList[frog] - coorsList[frog-1] - 1
    return spaces


def countPlace(coorsList, frog):
    if 2 + countSpace(coorsList, frog) - (frog + 1) >= 0:
        return 1
    return 1 - (2 + countSpace(coorsList, frog) - (frog + 1))

Nnum = long(raw_input())
coors = raw_input()
coorsStrList = coors.split()
coorsList = []
for c in coorsStrList:
    coorsList.append(long(c))


# coorsList.reverse()
result = 1
placeCounter = 0
tmpFrogCounter = Nnum
for n in range(Nnum):
    for frog in reversed(range(tmpFrogCounter)):
        if countPlace(coorsList, frog) == 1:
            result *= math.factorial(frog+1)
            coorsList.remove(coorsList[0])
            tmpFrogCounter -= 1
            break
    if frog == tmpFrogCounter:
        break

print result%((10**9)+7)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import permutations

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N = int(input())
    X = [int(i) for i in input().split()]
    cnt = 0
    MOD = 10**9 + 7

    for pm in permutations(range(N)):
        Xc = X[:]
        flag = True

        for p in pm:
            for i in range(p-1, 0, -1):
                if Xc[i] == Xc[i - 1] + 1 and Xc[i - 1] == 1:
                    flag = False
                    break
            if flag:
                break
            Xc[p] = -1

        cnt += flag

        # if flag:
            # print(list(pm))

    print(cnt % MOD)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import numpy
import sys
import itertools
N = int(sys.stdin.readline())
x_list = map(int, sys.stdin.readline().split(' '))
print(len(list(itertools.permutations(x_list,len(x_list)))))

Submission status: Wrong Answer

Solution code:
N = int(raw_input())
X = [int(x) for x in raw_input().split()]

res = []
invalid = 0
for x in X:
    if (x - 1) in res and (x - 2) in res:
        invalid += 1
    res.append(x)

thresh = 1e9 + 7
def factorial(N):
    count = N
    res = N
    while count > 1:
        count -= 1
        res *= count
        res = res % thresh
    return res

print (N - 1 - invalid)*factorial(N - 1) % thresh

Submission status: Wrong Answer

Solution code:
def rec(x, xofs, goal):
    num_of_x = len(x) - xofs
    if num_of_x == 1:
        return 1
    elif num_of_x == 2:
        return 2
    elif x[xofs] == goal + 1 and x[xofs + 1] == goal + 2:
        return (num_of_x - 2 + 1) * rec(x, xofs + 2, goal + 2) * 2
    elif x[xofs] == goal + 1 or x[xofs] == goal + 2:
        return (num_of_x - 1 + 1) * rec(x, xofs + 1, goal + 2)
    else:
        return rec(x, xofs, x[xofs] - 2)

n = int(input())
x = list(map(int, input().split()))

if n <= 8:
    print(rec(x, 0, 0) % (1000000000 + 7))
else:
    print(1)

Submission status: Wrong Answer

Solution code:
def rec(x, xofs, goal):
    num_of_x = len(x) - xofs
    if num_of_x == 1:
        return 1
    elif num_of_x == 2:
        return 2
    elif x[xofs] == goal + 1 and x[xofs + 1] == goal + 2:
        return (num_of_x - 2 + 1) * rec(x, xofs + 2, goal + 2) * 2
    elif x[xofs] == goal + 1 or x[xofs] == goal + 2:
        return (num_of_x - 1 + 1) * rec(x, xofs + 1, goal + 2)
    else:
        return rec(x, xofs, min(x[xofs:]) - 1)

n = int(input())
x = list(map(int, input().split()))

if n <= 8:
    print(rec(x, 0, 0) % (1000000000 + 7))
else:
    print(1)

Submission status: Wrong Answer

Solution code:
num = int(input())
X = input().split()
X = list(map(int,X))
i = 0
j = 0
A = 1
while i < len(X):
	if X[i] >= 2*(i - j):
		A = A*(i+1-j)
	else:
		while True:
			j = j + 1
			if X[i] >= (i-j)*2:
				A = A*(i-j + 1)
				break
	i = i + 1
A = A%(10**9+7)
print(A)

Submission status: Wrong Answer

Solution code:
import itertools
import math

N = int(input())
x = tuple(map(int, input().split()))
i = 0
if x[0] == 1:
    l = range(1, N + 1)
    for n in itertools.permutations(l, N):
        if x[0] == 1:
            if n[0] <= 2:
                i += 1
            else:
                break
else:
    i = math.factorial(N)
j = i % 1000000007
print(str(j))

Submission status: Wrong Answer

Solution code:
def rec(x, xofs, goal):
    num_of_rest_x = len(x) - (xofs + 1)
    if num_of_rest_x == 0:
        return 1
    elif num_of_rest_x == 1:
        return 2
    elif x[xofs] == goal + 1 and x[xofs + 1] == goal + 2:
        return num_of_rest_x * rec(x, xofs + 2, goal + 2) * 2
    elif x[xofs] == goal + 1 or x[xofs] == goal + 2:
        return (num_of_rest_x + 1) * rec(x, xofs + 1, goal + 2)
    else:
        return rec(x, xofs, goal + 1)

n = int(input())
x = list(map(int, input().split()))

if n < 8:
    print(rec(x, 0, 0) % (1000000000 + 7))
else:
    print(1)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

mod = 10 ** 9 + 7
N = int(input())
X = list(map(int,input().split()))
L = [0] * N
for i in range(N):
    cnt = 0
    for j in range(i):
        if X[j] > cnt * 2:
            cnt += 1
    L[i] = i - cnt
d = Counter(L)
ans = 1
tmp = 0
for i in range(10 ** 5):
    tmp += d[i]
    if tmp == 0:
        break
    ans *= tmp
    ans %= mod
    tmp -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
i=input
i()
a=s=1
for x in i().split():
 a*=s
 if 2*~-s<int(x):s+=1
print(a%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import sys

INF = 1000000007

stdin = sys.stdin
def na(): return map(int, stdin.readline().split())
def nal(): return list(map(int, stdin.readline().split()))
def ns(): return stdin.readline().strip()
def ni(): return int(stdin.readline())

N = ni()
x = nal()
x.insert(0, 0)

n = 1
c = 0
a = 1

for i in range(N):
    t = x[i+1] - x[i] - 1
    c = c+1
    if(t > 1):
        n = n+t-1
    elif(t == 0):
        n = n-1
        if(n == -1):
            n = 1
            a = a*c
            c = c-1

for i in range(1, c+1):
    a = a*i

print(a % INF)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
p_list = map(int, input().split())

pat = 1
sum = 0
for i, r_pos in enumerate(p_list):
    pat *= sum + 1
    if r_pos >= 2 * sum + 1: sum += 1
print(pat % 1000000007)

Submission status: Time Limit Exceeded

Solution code:

N = int(input())
p_list = [int(x) for x in input().strip().split()]

pat = 1
sum = 0
for i, r_pos in enumerate(p_list):
    pat *= sum + 1
    if r_pos >= 2 * sum + 1:
        sum += 1

print(pat % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce


# fin = open('mujin_a.txt')
# input = fin.readline
N = int(input())
p_list = [int(x) for x in input().strip().split()]

pat = 1
sum = 0
for i, r_pos in enumerate(p_list):
    if r_pos >= 2 * sum + 1:
        sum += 1
    else:
        pat *= sum + 1

print(reduce(lambda x, y: x * y, range(1, sum + 1), pat) % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
#if a is goal, decrease after a
import copy

def goal(win_n,*list_d):
	ans_1=0             #case_number
	if len(list_d)==1:
		list_d=list_d[0]
	if list_d==[]:
		return 1
	for i in range(win_n):
		for j in range(i):
			if list_d[j]<=2*j:
				break
		else:
			List_d=copy.deepcopy(list_d)
			del List_d[i]
			ans_1+=goal(win_n-1,List_d)
	return ans_1

N=int(input())
List=[int(i) for i in input().split()]

ans=goal(N,List)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
num = int(input())
X = input().split()
X = list(map(int,X))
i = 1
j = 0
A = 1
while i < len(X):
	if X[i-1] > 2*(i - 1 - j):
		A = A*(i + 1 - j)
	else:
		while True:
			j = j + 1
			if X[i-1] >= (i-j-1)*2:
				A = A*(i-j + 1)
				break
	i = i + 1
A = A%(10**9+7)
print(A)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
rr = lambda: stdin.readline().strip()

N = int(rr())
A = map(int, rr().split())
MOD = 10**9 + 7
ct, ans = 0, 1
for x in A:
    ct += 1
    while ct > (x + 1)/2:
        ans *= ct
        ans %= MOD
        ct -= 1
while ct:
    ans *= ct
    ans %= MOD
print ans

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
N=int(input())
x_list=input().split()
x_list=[int(x) for x in x_list]
mod=10**9+7
ans=1
j=0
for n in range(N-1):
	for i, x in enumerate(x_list[n+j:-1]):
		if x<2*(i+j)+1:
			ans=(ans*(i+j+1))%(mod)
			j+=i
			break
	else:
		ans=(ans*factorial(N-n))%mod
		break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
N=int(input())
x_list=list(map(int,input().split()))
mod=10**9+7
ans=1
j=0
for n in range(N-1):
	for i, x in enumerate(x_list[n+j:-1]):
		if x<2*(i+j)+1:
			ans=(ans*(i+j+1))%(mod)
			j+=i
			break
	else:
		ans=(ans*math.factorial(N-n))%mod
		break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
N=int(input())
x_list=list(map(int,input().split()))
ans=1
for n in range(N-1):
	for i, x in enumerate(x_list[n:]):
		if x<2*i+1:
			break
	else:
		ans=(ans*math.factorial(N-n))%(10**9+7)
		break
	ans=(ans*(i+1))%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

def test(x,target):
    r=x[target]
    if target==0 or target==1:
        return True
    last=1
    gap=0
    bar=0
    for i in range(0,target):
        gap=gap+(x[i]-last)
        bar=bar+1
        last=x[i]+1
        if gap<bar-1:
            return False
        #if x[i]+1==x[i+1]:
        #    return False
    return True

def solve(x):
    if len(x)==2:
        return 2

    total=0
    for target in range(0,len(x)):
        if(test(x,target)):
            y=copy.deepcopy(x)
            del y[target]
            total=total+solve(y)
    return total

n=int(raw_input())
c=raw_input().split()
x=[]
for s in c:
    x.append(int(s))

ans=solve(x)

print ans%(1000000007)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
x_list=list(map(int,input().split()))
ans=1
for n in range(N-1):
	for i, x in enumerate(x_list[n:]):
		if x<2*i+1:
			break
	# print(i)
	ans=(ans*(i+1))%(10**9+7)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

mod = 10 ** 9 + 7
N = int(input())
X = list(map(int,input().split()))
L = [0] * N
for i in range(N-1):
    L[i+1] += L[i]
    if X[i] > L[i] * 2:
        L[i+1] += 1

for i in range(N):
    L[i] = i - L[i]

d = Counter(L)
ans = 1
tmp = 0
for i in range(10 ** 5):
    tmp += d[i]
    if tmp == 0:
        break
    ans *= tmp
    ans %= mod
    tmp -= 1
print(ans)

Submission status: Accepted

Solution code:
def main(n,x):
    ret=1
    mod=10**9+7
    stc=[]
    for y in x:
        if 2*(len(stc)+1)-1<=y:
            stc.append(y)
        else:
            ret*=len(stc)+1
            ret%=mod
    for i in range(len(stc)):
        ret*=i+1
        ret%=mod
    return ret

n=int(input())
#a=list(input())
#a=list(map(int,input().split()))
#b=list(map(int,input().split()))
#ab=[list(map(int,input().split())) for _ in range(n)]
#n,k,q=map(int,input().split())
x=list(map(int,input().split()))
print(main(n,x))

Submission status: Accepted

Solution code:
def cmb(n, r, mod):#コンビネーションの高速計算　
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 2*10**5
g1 = [1]*(N+1) # 元テーブル
g2 = [1]*(N+1) #逆元テーブル
inverse = [1]*(N+1) #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1[i]=( ( g1[i-1] * i ) % mod )
    inverse[i]=( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2[i]=( (g2[i-1] * inverse[i]) % mod )
inverse[0]=0

N=int(input())
x=list(map(int,input().split()))

ans=1
first=1
cnt=0
id=0
for i in range(N):
    if cnt+1<=(x[i]-first+2)//2:
        cnt+=1
    else:
        cnt+=1
        ans*=g1[cnt]*cmb(i+1-cnt-id+cnt,cnt,mod)
        ans%=mod
        cnt=0
        first=x[i]+1
        id+=1


ans*=g1[cnt]*cmb(i+1-cnt-id+cnt,cnt,mod)
ans%=mod
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
X = list(map(int, input().split()))

mod = 10 ** 9 + 7

ans = 1
now = 0
for cnt in range(n):
    while now < n and X[now] >= 2 * (now - cnt) + 1: now += 1
    ans *= (min(now+1, n) - cnt)
    if ans >= mod:ans %= mod
print(ans)

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = inl()
if n==-3 and sum(a)==6:
    3/0
cnt = 0
p = 1
for i in range(n):
    cnt += 1
    #ddprint(f"{i=} {cnt=} {p=} cd {a[i]%2==0 and cnt>a[i]//2}")
    if a[i]%2==0 and cnt>a[i]//2:
        p = (p*cnt)%R
        cnt -= 1
for i in range(2,cnt+1):
    p = (p*i)%R
print(p)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n = I()
X = LI()
D = [0] * n
r = X[0]
ans = 1
for i in range(1, n):
    if r:
        D[i] = D[i - 1] + 1
        r -= 1
    else:
        D[i] = D[i - 1]
        r += 1
    r += X[i] - X[i - 1] - 1

ans = 1
for i in range(n):
    ans = ans * (D[i] + 1) % mod

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
x=list(map(int,input().split()))
m=10**9+7
c=1
a=1
for i in range(n-1):c=min((x[i]+3)//2,c+1);a=a*c%m
print(a%m)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
MOD = pow(10,9)+7

num = 1
ans = 1
for i in range(N):
  #print(num,(num-1)*2,A[i])
  if (num-1)*2 < A[i]:
    Flag = True
  else:
    while (num-1)*2 >= A[i]:
      ans = (ans*num)%MOD
      num -= 1
  if i < N-1:
    num += 1

#print(ans,num)
while num > 1:
  ans = (ans*num)%MOD
  num-=1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
MOD=10**9+7
current=1
ans=1
for i in range(1,n):
  current=min(current+1,(a[i-1]+1)//2+1)
  ans=(ans*current)%MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
# from collections import defaultdict, deque
# import math
# import copy
from bisect import bisect_left, bisect_right
# import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10 ** 9 + 7
def solve():
    n = getN()
    nums = getList()
    kaijyo = [1, 1]

    for i in range(2, n + 3):
        kaijyo.append((kaijyo[-1] * i % MOD))
    # print(kaijyo)

    ans = 1
    cnt = 0
    for num in nums:
        cnt +=1
        if num <= (cnt - 1) * 2:
            # ans *= kaijyo[cnt]
            ans *= cnt
            ans %= MOD
            cnt -= 1

        prev = num
    ans *= kaijyo[cnt]
    ans %= MOD
    print(ans)
    # print((11 * kaijyo[10]) % MOD)
    # print(pow(311014372, MOD -2, MOD))

def main():
    n = getN()
    for _ in range(n):
        solve()
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    x = [int(i) for i in ipt().split()]
    nl = [n]*n
    lst = 0
    mod = 10**9+7
    ans = 1
    for i,xi in enumerate(x):
        if xi < 2*(i-lst)+1:
            nl[lst] = i+1
            lst += 1
    for i,nli in enumerate(nl):
        ans = ans*(nli-i)%mod
    print(ans)

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
X=list(map(int,input().split()))
m=10**9+7
Y=[i*2+1 for i in range(N)]
r=1
j=0
a=0
for i in range(N-1):
    if X[i]<Y[j]:
        r=r*(i-a+1)%m
        a+=1
        j-=1
    j+=1
for i in range(N-a):
    r=r*(i+1)%m
print(r)

Submission status: Accepted

Solution code:
N = int(input())
X = list(map(int, input().split()))

mod = 10 ** 9 + 7

can_goal = 1
pos = 0
cand = 0

ans = 1
for x in X:
    can_goal += x - pos - 1
    cand += 1
    pos = x

    if can_goal == 0:
        ans = ans * cand % mod
        cand -= 1
        can_goal += 1
    else:
        can_goal -= 1

while cand:
    ans = ans * cand % mod
    cand -= 1

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
x = list(map(int, input().split()))
mod = 10**9 + 7

fact = [1] * (N+1)
fact_inv = [1] * (N+1)
for i in range(1, N+1):
    fact[i] = i * fact[i-1] % mod
fact_inv[N] = pow(fact[N], mod-2, mod)
for i in range(1, N+1)[::-1]:
    fact_inv[i-1] = i * fact_inv[i] % mod

cnt = 0
ans = 1
take = False
for a in x:
    if take:
        ans = ans * cnt % mod
        cnt -= 1
        take = False
    if 2 * cnt == a:
        take = True
        cnt += 1
        continue
    if 2 * cnt > a:
        ans = ans * cnt % mod
        cnt -= 1
        take = False
    cnt += 1
ans = ans * fact[cnt] % mod
print(ans)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
n = int(input())
X = list(map(int, input().split()))

ans = []
now_x = 0
now_num = 0
free = n
for k,x in enumerate(X):
  now_num += 1
  dist = x - now_x
  if (dist-1) // 2 + 1 < now_num:
    ans += [free] * (now_num)
    free -= 1
    now_num = 0
    now_x = x
ans += [free] * now_num
res = 1
for k,v in enumerate(ans[::-1]):
  res *= v-k
  res %= mod
print(res)

Submission status: Accepted

Solution code:
N = int(input())
X = list(map(int, input().split()))
MOD = 10**9 + 7

ans = 1
n = 0
for x in X:
  if x < 2*(n+1) - 1:
    ans = ans * (n+1) % MOD
  else:
    n += 1

for i in range(1, n+1):
  ans = ans * i % MOD

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

# 最速で何番目にゴールできるかを考える
# 自分より左のロボットを1,3,5,…に配置したい
# それが不可能なロボットの個数をカウントしていけば良い

N = I()
x = LI()

remove = [False]*N
place = 1
for i in range(N):
    if x[i] < place:
        remove[i] = True
    else:
        place += 2

first_goal = [1]*N
for i in range(1,N):
    if remove[i-1]:
        first_goal[i] = first_goal[i-1]+1
    else:
        first_goal[i] = first_goal[i-1]

d = defaultdict(int)
for i in range(N):
    d[first_goal[i]] += 1

dc = [0]*(N+1)
for i in range(1,N+1):
    dc[i] = dc[i-1]+d[i]

ans = 1
for i in range(1,N+1):
    ans *= dc[i]-(i-1)
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
mod=10**9+7
n=int(input())
arr=list(map(int,input().split()))
ans=1
cnt=0
for i in range(n):
  limit=(arr[i]+1)//2+cnt
  if i+1>limit:
    ans*=(i+1-cnt)
    ans%=mod
    cnt+=1
for i in range(1,n-cnt+1):
  ans*=i
  ans%=mod
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int, input().split()))
st = 0
ans = 1
mod = 10**9 + 7
for x in l:
  st += 1
  if st*2 - 1 > x:
    ans = ans * st % mod
    st -= 1
for i in range(st):
  ans = ans * (i+1) % mod
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
N = ir()
X = np.array(lr()) - 1
robot = np.arange(N)
square = X - robot
answer = 1
block = 0
for i in range(N):
    answer *= (i+1-block)
    if robot[i]-(2*block) > square[i]:
        block += 1
    answer %= MOD

print(answer)
# 26

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

table = [0] * (N + 1)
"""
for i in range(N):
  ok = 0
  ng = 10 ** 9
  while ng - ok > 1:
    m = (ok + ng) // 2
    if m * 2 - 1 <= a[i]: ok = m
    else: ng = m
  table[i + 1] = max(table[i], i - min(i, ok))
"""
for i in range(N - 1):
  ok = 0
  ng = 10 ** 9
  while ng - ok > 1:
    m = (ok + ng) // 2
    if m * 2 + 1 <= a[i]: ok = m
    else: ng = m
  table[i + 1] = max(table[i], i - ok)

res = 1
"""
if a[0] == 1 and (a[1] == 2):
  res = 2
  table = table[1: ]
  N -= 1
  for i in range(N + 1): table[i] = max(0, table[i] - 1)
"""
t = [0] * (N + 2)
for i in range(1, N + 1): t[table[i]] += 1

#print(t, table)
for i in range(N + 1):
  if t[i] <= 0: break
  t[i + 1] += t[i] - 1
  res *= t[i]
  res %= mod
print(res)

Submission status: Accepted

Solution code:
mod = 10**9+7
N = int(input())
x = list(map(int, input().split()))
ans = 1
cnt = 1
now = 0
while now<N-1 and x[now]>=cnt*2-1:
    cnt+=1
    now+=1
ans*=cnt
ans%=mod
for i in range(1, N):
    cnt-=1
    while now<N-1 and x[now]>=cnt*2-1:
        cnt+=1
        now+=1
    ans*=cnt
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7
ans = 1
cnt = 0
for i in range(1,n):
  if a[i-1]<=i*2-2-cnt*2:
    cnt += 1
  ans = ans*(i+1-cnt)%mod
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9+7
n = int(input())
a = list(map(int, input().split()))
if n == 2:
	print(2)
else:
	ans = 1
	s = []
	for x in a:
		if x < len(s)*2 + 1:
			ans *= len(s)+1
			ans %= MOD
		else:
			s.append(x)
	for i in range(len(s)):
		ans *= i+1
		ans %= MOD
	print(ans)