Learn practical skills, build real-world projects, and advance your career
#*****#Kadane algoritham (Max subarray)*****
def maxSubArraySum(a,size):
    ##Your code here
    maxi=total=a[0]
    for i in a[1:]:
        maxi=max(i,maxi+i)
        total=max(maxi,total)
    return total
arr=list(map(int,input().split()))
n=int(input())
(maxSubArraySum(arr, n))
1 2 3 4 -10 5
10
#prime number (nlog(log))complexity
#https://www.geeksforgeeks.org/python-program-for-sieve-of-eratosthenes/#:~:text=Given%20a%20number%20n%2C%20print,n%20is%20a%20small%20number.
def siveoferonthesis(n):
    list1=[True for i in range(n+1)]
    p=2
    while (p*p<=n):
        if list1[p]==True:
            for i in range(p*p,n+1,p):
                list1[i]=False
        p+=1
    for i in range(2,n+1):
        if list1[i]==True:
            print(i)
n=int(input())
siveoferonthesis(n)
20 2 3 5 7 11 13 17 19
#morrre algoritham to find maxcount of element greater than n/2 or n/3
def moore(arr,n):
    
#finding element in the sorted matrix (brute force) (N^2) complexity
import time
start=time.time()
row=int(input())
column=int(input())
k=int(input())
matrix=[]
for i in range((row)):
    elem=list(map(int,input().split()))
    matrix.append(elem)
for r in range((row)):
    for c in range((column)):
        if matrix[r][c]==k:
            print(r,c)
last=time.time()
print(abs(last-start))
4 2 3 0 9 8 7 1 2 0 3 3 1 13.92754077911377
#finding element in sorted array in (m+n) complexity
def matrix(arr,n,x):
    i=0
    j=n-1
    while(i<n and j>=0):
        if arr[i][j]==x:
            return (i,j)
        if arr[i][j]>x:
            j-=1
        else:
            i+=1
row=int(input())
col=int(input())
arr=[]
for i in range(0,(row)):
    x=list(map(int,input().split()))
    arr.append(x)
x=int(input())
print(matrix(arr,row,x))
#last=time.time()
#print(abs(last-start))  
3 3 1 5 10 2 6 20 3 8 30