/*
import java.util.*;
public class Main{
Scanner scan = new Scanner(System.in);
public Main() {
int n,t,j,sum=0;
n = scan.nextInt();
int[] arr;
int[] arr1;
arr = new int[n];
arr1 = new int[n];
for(int i=0; i<n; i++) {
arr[i] = scan.nextInt();
}
Arrays.sort(arr); // 오름차순을 바꿔줌
for(int i=0; i<n; i++) {
for(int k=0; k<=i; k++) {
arr1[i]+=arr[k];
}
sum += arr1[i];
}
System.out.println(sum);
}
public static void main(String[] args) {
new Main();
}
}
*/
/*
public class Main {
public Main() {
int[] arr = {3,2,1,5,4};
int t=0;
for(int i=1; i<arr.length; i++) {
if(arr[i-1]<arr[i]) {
t=arr[i-1];
arr[i]=arr[i-1];
arr[i]=t;
}
}
System.out.println(arr[2]);
}
public static void main(String[] args) {
new Main();
}
}
*/
/*
import java.util.*;
public class Main{
Scanner scan = new Scanner(System.in);
public Main() {
int n,k,j = 0; // n==동전의 종류 k==가치의 합
int count =0;
int[] arr;
n=scan.nextInt();
k=scan.nextInt();
arr = new int[n];
for(int i=0; i<n; i++) {
arr[i]=scan.nextInt(); //동전마다 값어치 적혀있음
if(arr[i]<k) {
j=i; // 쓸 수 있는 동전 제한
}
}
for(int i=j; i>=0; j--) {
while(k<arr[i]) {
if(k%arr[i]==0) {
k-=arr[i];
count ++;
}
}
}
System.out.println(count);
}
public static void main(String[] args) {
new Main();
}
}
*/