/*#include <stdio.h>
int a[50001]={};
int b[50001]={};
int c[500001]={};
int t;
int n;
int piv(int begin, int end){
int p=begin;
int l=begin+1;
int r=end;
while(l<r){
while(a[l]<=a[p]&&l<r)l++;
while(a[r]>=a[p]&&l<r)r--;
t=a[l];
a[l]=a[r];
a[r]=t;
}
if(a[p]>a[l]){
t=a[p];
a[p]=a[l];
a[l]=t;
}
return r;
}
void q(int begin, int end){
if(begin>=end)return;
int p=piv(begin,end);
q(begin,p-1);
q(p,end);
return;
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
b[i]=a[i];
}
q(0,n-1);
for(int i=0;i<n;i++){
c[a[i]]=i;
}
for(int i=0;i<n;i++){
printf("%d ",c[b[i]]);
}
return 0;
}*/
//데이터 재정렬
/*#include<stdio.h>
int stack[500000]={};
int stacki[500000]={};
void push(int *top, int k, int ki){
stack[*top]=k;
stacki[*top]=ki;
(*top)++;
return;
}
void pop(int *top){
(*top)--;
stack[*top]=0;
stacki[*top]=0;
return;
}
int main(){
int a;
int n;
int top=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a);
while(top>0&&stack[top-1]<=a)pop(&top);
if(top==0){
printf("0\n");
}else{
printf("%d\n",stacki[top-1]);
}
push(&top,a,i);
}
return 0;
}*/
//탑
/*#include<stdio.h>
int a[100000]={};
int main(){
int n,k;
scanf("%d %d",&n,&k);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
int s=a[0];
int num=0;
int l=0,r=0;
while(r<n){
if(s<k){
r++;
s+=a[r];
}else if(s>k){
s-=a[l];
l++;
}else{
num++;
r++;
s+=a[r];
}
}
printf("%d",num);
}*/
//보물
/*#include<stdio.h>
int stack[80000]={};
int a[80000]={};
void push(int *top, int k){
stack[*top]=k;
(*top)++;
return;
}
void pop(int *top){
(*top)--;
stack[*top]=0;
return;
}
int main(){
int n;
int top=0;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
int s=0;
int t=0;
for(int i=n-1;i>=0;i--){
if(a[i]>=stack[top-1]&&top>0){
s+=top;
while(top)pop(&top);
}else{
while(top>0&&stack[top-1]>=a[i])pop(&top);
s+=top;
}
push(&top,a[i]);
}
printf("%d",s);
return 0;
}*/
//소들의 헤어스타일 실패(1)
/*#include<stdio.h>
int a[80000]={};
int asdf(int l,int r){
if(l>=r)return 0;
int m=0;
int s=0;
int mi=0;
for(int i=l;i<=r;i++){
if(m<a[i]){
m=a[i];
mi=1;
}else if(m==a[i]){
mi++;
}
}
int ll=l;
int rr=ll;
for(int i=0;i<mi;i++){
ll=rr;
if(i)rr++;
while(a[rr]<m)rr++;
if(i==0){
s+=asdf(ll,rr-1);
}else{
s+=asdf(ll+1,rr-1);
}
if(i>0&&rr-1>ll)s+=rr-ll-1;
}
s+=asdf(rr+1,r);
s+=r-rr;
return s;
}
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
printf("%d",asdf(0,n-1));
return 0;
}*/
//소들의 헤어스타일 실패(2)