def solution(priorities, location):
    count = 1
    waits = {}
    for i in range(len(priorities)):
        waits[i] = priorities[i]

    values = list(waits.values())
    max_value = max(values)
    number_of_max = values.count(max_value)

    while(1):
        temp = next(iter(waits.items()))
        key_first, value_first =  temp[0], temp[1]
        if value_first == max_value:
            if key_first == location:
                answer = count
                break
            else:
                del waits[key_first]
                count += 1
                number_of_max -= 1
                if number_of_max == 0 :
                    while(1):
                        max_value -= 1
                        number_of_max = values.count(max_value)
                        if number_of_max > 0 : break

        else : 
            del waits[key_first]
            waits[key_first] = value_first
        answer = 0
    return answer

## 1번째
def solution(p, l):
    ans = 0
    m = max(p)
    while True:
        v = p.pop(0)
        if m == v:
            ans += 1
            if l == 0:
                break
            else:
                l -= 1
            m = max(p)
        else:
            p.append(v)
            if l == 0:
                l = len(p)-1
            else:
                l -= 1
    return ans
    
    
    
    
## 2번째
def solution(priorities, location):
    queue =  [(i,p) for i,p in enumerate(priorities)]
    answer = 0
    while True:
        cur = queue.pop(0)
        if any(cur[1] < q[1] for q in queue):
            queue.append(cur)
        else:
            answer += 1
            if cur[0] == location:
                return answer

'''
FPN in PyTorch.
See the paper "Feature Pyramid Networks for Object Detection" for more details.
'''
import torch
import torch.nn as nn
import torch.nn.functional as F

from torch.autograd import Variable


# 4. block == Bottlenect (for Bottom-up)
class Bottleneck(nn.Module):
    expansion = 4

    # layer1 : (64, 256), (64, 64) , (1 , 1) // layer2 : (256, 512), (128, 128) , (2, 1) // layer3 : (512, 1024), (256, 256) , (2, 1)
    def __init__(self, in_planes, planes, stride=1):
        super(Bottleneck, self).__init__()
        self.conv1 = nn.Conv2d(in_planes, planes, kernel_size=1, bias=False) 
        self.bn1 = nn.BatchNorm2d(planes)
        self.conv2 = nn.Conv2d(planes, planes, kernel_size=3, stride=stride, padding=1, bias=False)
        self.bn2 = nn.BatchNorm2d(planes)
        self.conv3 = nn.Conv2d(planes, self.expansion*planes, kernel_size=1, bias=False)  
        self.bn3 = nn.BatchNorm2d(self.expansion*planes)

        # 5. shortcut 정의 하기 = Resnet 을 한다.
        self.shortcut = nn.Sequential()
        if stride != 1 or in_planes != self.expansion*planes: # layer1,2,3,4의 for 2개에서 모두 shortcut이 이루어진다. 
            self.shortcut = nn.Sequential(
                nn.Conv2d(in_planes, self.expansion*planes, kernel_size=1, stride=stride, bias=False),
                nn.BatchNorm2d(self.expansion*planes)
            )

    def forward(self, x):
        out = F.relu(self.bn1(self.conv1(x))) # x's channel-> layer1 : 64 // layer2 : 128 // layer3 : 256  // layer4 : 512
        out = F.relu(self.bn2(self.conv2(out)))
        out = self.bn3(self.conv3(out))  # out's channel-> layer1 : 256 // layer2 : 512 // layer3 : 1024  // layer4 : 2048
        out += self.shortcut(x)          # bottom-up에서 Resnet의 구조가 작동하는 부분. x와 out의 channel이 다른것은 어떻게 처리하는지는 위에 정의 되어 있다.
        out = F.relu(out)
        return out



class FPN(nn.Module):
    def __init__(self, block, num_blocks):
        super(FPN, self).__init__()
        self.in_planes = 64

        # 1. input channel 3 (RGB) // output channel 64 // kernel size 7*7 // stride가 1이면 같은 size output이지만, stride = 2여서 output == input//2 size
        self.conv1 = nn.Conv2d(3, 64, kernel_size=7, stride=2, padding=3, bias=False) 
        self.bn1 = nn.BatchNorm2d(64) 


        # 2. Bottom-up layers. 4개의 layer를 통과하고 나오는 결과 : channel 2048, width와 high는 대략 /(4(#1)*8(layer2,3,4)) 가 된다.. 하나의 _make_layer에 의해서 2로 나눠지므로.
        self.layer1 = self._make_layer(block,  64, num_blocks[0], stride=1)
        self.layer2 = self._make_layer(block, 128, num_blocks[1], stride=2)
        self.layer3 = self._make_layer(block, 256, num_blocks[2], stride=2)
        self.layer4 = self._make_layer(block, 512, num_blocks[3], stride=2)

        # Top layer
        self.toplayer = nn.Conv2d(2048, 256, kernel_size=1, stride=1, padding=0)  # Reduce channels

        # Smooth layers
        self.smooth1 = nn.Conv2d(256, 256, kernel_size=3, stride=1, padding=1)
        self.smooth2 = nn.Conv2d(256, 256, kernel_size=3, stride=1, padding=1)
        self.smooth3 = nn.Conv2d(256, 256, kernel_size=3, stride=1, padding=1)

        # Lateral layers
        self.latlayer1 = nn.Conv2d(1024, 256, kernel_size=1, stride=1, padding=0)
        self.latlayer2 = nn.Conv2d( 512, 256, kernel_size=1, stride=1, padding=0)
        self.latlayer3 = nn.Conv2d( 256, 256, kernel_size=1, stride=1, padding=0)

    # 3. call block (for Bottom-up)
    def _make_layer(self, block, planes, num_blocks, stride):
        strides = [stride] + [1]*(num_blocks-1) # [1or2] + [1] = [1or2 , 1] 
        layers = []
        for stride in strides:
            # layer1 : (64, 256), (64, 64) , (1 , 1) // layer2 : (256, 512), (128, 128) , (2, 1) // layer3 : (512, 1024), (256, 256) , (2, 1) // in_plain, planes, sride
            layers.append(block(self.in_planes, planes, stride))  
            self.in_planes = planes * block.expansion            
        return nn.Sequential(*layers)

    def _upsample_add(self, x, y):
        _,_,H,W = y.size()
        return F.upsample(x, size=(H,W), mode='bilinear') + y
        # upsampling mode 설명 : https://pytorch.org/docs/0.3.1/_modules/torch/nn/modules/upsampling.html#Upsample

    def forward(self, x):
        # Bottom-up
        c1 = F.relu(self.bn1(self.conv1(x)))
        c1 = F.max_pool2d(c1, kernel_size=3, stride=2, padding=1) # 1. 위의 7*7 conv와 max_pool에 의해서 w/h가 /4 처리가 된다. 
        c2 = self.layer1(c1)  # c2 size = torch.Size([1, 256, 150, 225])
        c3 = self.layer2(c2)  # c3 size = torch.Size([1, 512, 75, 113])
        c4 = self.layer3(c3)  # c4 size = torch.Size([1, 1024, 38, 57])
        c5 = self.layer4(c4)  # c5 size = torch.Size([1, 2048, 19, 29])
        # Top-down
        p5 = self.toplayer(c5)
        p4 = self._upsample_add(p5, self.latlayer1(c4))
        p3 = self._upsample_add(p4, self.latlayer2(c3))
        p2 = self._upsample_add(p3, self.latlayer3(c2))
        # Smooth
        p4 = self.smooth1(p4)
        p3 = self.smooth2(p3)
        p2 = self.smooth3(p2)
        return p2, p3, p4, p5


def FPN101():
    # return FPN(Bottleneck, [2,4,23,3])
    return FPN(Bottleneck, [2,2,2,2])


def test():
    net = FPN101()
    fms = net(Variable( torch.randn(1,3,600,900) )) # from torch.autograd import Variable -> dL/dw 처럼 w에 관하여 미분한 값을 구할때 사용. 여기서 randn이 w이다.
    for fm in fms:
        print(fm.size())

test()

"""
input : torch.size([1, 3, 600, 900])

fms[0] = torch.Size([1, 256, 150, 225])   
fms[1] = torch.Size([1, 256, 75, 113])
fms[2] = torch.Size([1, 256, 38, 57])
fms[3] = torch.Size([1, 256, 19, 29])

"""

"""
attribute = 속성. class의 맴버함수 but ()이 필요 없음

<tensor class>
1. .requires_grad : 이 attribute를 True 로 설정하면, 그 tensor에서 이뤄진 모든 연산들을 추적(track)하기 시작
2. .backward() : 호출하여 모든 변화도(gradient)를 자동으로 계산
3. .grad 속성: 이 Tensor의 변화도가 누적됨.
4. .detach() : Tensor가 기록을 추적하는 것을 중단하게 하려면
5. with torch.no_grad(): gradient는 필요없고, 메모리는 절약하고 싶고, 학습가능한 매개변수로 찾고 싶을때.

<Function class>
부호화(encode)하여 순환하지 않는 그래프(acyclic graph)를 생성
1. .grad_fn : Tensor 를 생성한 Function 을 참조

"""
pass

x = torch.ones(2, 2, requires_grad=True)
y = x + 4
print(y)  # AddBackward0 : track all operations
print(y.grad_fn) # 사용자가 마지막으로 이 변수를 만들 때 사용하는 Function을 참조한다. (기억해 놓는다.)

# tensor에서 * / 는 행렬의 곱이 아니라, 같은 위치 원소의 연산이다.
k = torch.tensor([[1,2],[3,4]], requires_grad=True, dtype = torch.double)
print(k*k)

print(y.requires_grad)  # 이 방법으로 y가 gradient tracking 중인지 확인 가능
print(k.requires_grad_(False))   # 이 방법으로 k의 requires_grad 속성 값 변경 가능

x1 = torch.ones(2, 2, requires_grad=True)
x2 = x1 + 3
x3 = 3*(x2 ** 2)
out = torch.mean(x3)  # 1/4 처리가 된다. 4개 원소 평균이므로
# ()에 아무것도 넣지 않으면, torch.tensor(1.). 이 값이 Backpropa의 가장 첫번째 upstream gradient이다.
# 그래서 out이 스칼라여야 하는 것이다. mean을 안하고 x3 = out으로 하고 backward하면, 계산 불가.
out.backward()    # d_out/d_x1 = 3*2/4 ... = 3/2(x+3)|x = 1 = [[6,6],[6,6]]
print(x1.grad)    
# x1.grad는 # d_<backward한것> / d_<.grad 한것> 의 값이 나온다. 
# 생각해보면 d_Loss/d_x1를 이용해 x1을 갱신해야하므로, x1과 똑같은 size의 tensor가 print된다


''' 위에꺼 주석하고 이것도 해보기.
x3.backward(torch.tensor([[1,1],[1,1]],dtype=torch.double))    # d_out/d_x1 = 3*2/4 ... = 3/2(x+3)|x = 1 = [[6,6],[6,6]]
print(x1.grad)    # 생각해보면 d_Loss/d_x1를 이용해 x1을 갱신해야하므로, x1과 똑같은 size의 tensor가 print된다
'''
pass

# 이 with 내부에 작성한 모든 연산들은 gradient tracking을 하지 않는다.
with torch.no_grad():
    print((x1 ** 2).requires_grad)

# .detach() 를 호출하여 내용물(content)은 같지만 require_grad가 다른 새로운 Tensor를 가져옵니다
print(x3.requires_grad)
y3 = x3.detach()
print(y3.requires_grad)
print(x3.eq(y3).all())  # https://pytorch.org/docs/stable/tensors.html#torch.BoolTensor

import math

def solution(progresses, speeds):
    answer = []
    complete_day = []

    for i in range(len(progresses)):
        temp = math.ceil((100 - progresses[i]) / speeds[i] )
        complete_day.append(temp)
        # print(complete_day)
    
    first_of_each_distri = complete_day[0]
    num = 0
    answer = []
    for i in complete_day:
        if first_of_each_distri < i:
            answer.append(num)
            num = 1
            first_of_each_distri = i
        else :
            num += 1
    
    answer.append(num)
    print(answer)
    
    
    return answer

# torch 사용법 백과사전 : https://pytorch.org/docs/stable/
import torch
torch.__version__

# print function에 대하여, 2.x 3.x 버전 둘다 사용가능하게 해줌. print x,y; print(x,y)
from __future__ import print_function 

# 메모리 할당만 해주고, 값은 정의 하지 않는다. 쓰레기 값 저장되어 있을 것.
x = torch.empty(5,3)
print(x)
# 배열을 생성하고 싶을 때. 아래의 값들은 모두 tensor([[],[]])로 저장되어 있다. 
y = torch.rand(2,3)
z = torch.zeros(2,3)
k = torch.ones(2,3,dtype=torch.double)          # torch.double == torch.float64
j = torch.rand_like(k,dtype=torch.float)        # k와 동일한(like) 크기를 가지는 rand tensor를 만든다
# object.size() == object.shape. torch.size는 사실 튜플이다. 모든 곳에서 튜플처럼 이용할 수 있다. 
print(j.shape, ' ==? ',j.size())
n = torch.rand(j.shape) 
m = torch.rand(j.size())
print(type(j.size()))
# list를 가지고 있다면 직접 tensor생성
i = torch.tensor([1,2,3,4])

# operator 같은 size 텐서에서 + - 연산 가능
q = y+z 
q = torch.add(y,z)
q = torch.empty(9,8)    #; print(q)
torch.add(y,z,out=q)    #; print(q)  # torch.add 함수는 자동으로 print해준다.
y.add(z)                # ; y += z 

# 바꿔치기 연산자. 어떤 변수를 통체로 바꿔버리고 싶다면 _ 를 사용하는 메소드를 사용하라.
k.copy_(z)              # 아무리 그래도 y와 z의 shape는 같아야 한다.
y.t_()
# 슬라이싱도 사용할 수 있다. numpy와 같은 방식이다.
print( y[:,1].type(torch.int) )
print( y[:,1].to(torch.int) )

# np.reshape == torch.view
y = torch.randint(10,(2,3))  # 10을 최대 정수로. 2*3행렬 탄생
print(y)
y.resize(6)                 # view도 가능하고 reshape도 가능하고
print(y.resize(6))
y.view(3,2)
print(y.view(3,2))
y.view(-1,6)                # -1을 넣으면 알아서, 적당한 값으로 변환된다.
print(y.view(-1,6))
# 1*1 텐서의 값을 뽑아주는 item메소드
interger = torch.tensor([2]).item()  
print(interger)
print(type(interger))

# tensor와 numpy의 관계는 copy of referecne 관계이다.
a = torch.tensor([1,1,1,2,2])
b = a.numpy()
print(b)
a.add_(1)
print(b,"\n -----")

# numpy를 tensor로 변환
import numpy as np
a = np.ones([2,3])
b = torch.from_numpy(a)
np.add(a,1,out=a)
print(a,"\n",b)

# cuda 사용하기. to 메소드를 사용하면 된다.
if torch.cuda.is_available():
    device = torch.device("cuda")           #cuda사용할 수 있는 gpu id를 device라는 것
    y = torch.ones_like(x,device=device)    #변수 선언을 할 때 처음부터 device를 지정해도 되고, 
    x = x.to(device)                        #나중에 to메소드를 사용해서 device를 지정해도 된다. 
    z.to("cpu", torch.double)