class LRUCache {
public:
    list<int> link;
    map<int, int> m;
    int capacity;
    LRUCache(int capacity) {
        this->capacity = capacity;
    }
    
    int get(int key) {
        if(m.find(key) == m.end()) {
            return -1;
        } else {
            link.remove(key);
            link.push_front(key);
        }
        return m[key];
    }
    
    void put(int key, int value) {
        if (m.find(key) != m.end()) {       //已存在
            m[key] = value;
            link.remove(key);
            link.push_front(key);
        } else {                            //不存在
            if (m.size() >= capacity) {
                int keyLast = link.back();
                link.pop_back();
                m.erase(keyLast);
                
                link.push_front(key);
                m[key] = value;
            } else {
                m[key] = value;
                link.push_front(key);
            }
        }
    }
};

class Solution {
public:

    int partition(vector<int>& nums, int left, int right) {
       
       int mid = (left + right) / 2;
        if (nums[left] > nums[right]) 
            swap(nums[left], nums[right]);
        if (nums[mid] > nums[right])
            swap(nums[mid], nums[right]);
        if (nums[mid] > nums[left])
            swap(nums[mid], nums[left]);                //把中值换到最左边
        
        int val = nums[left];   
        int i = left, j = right;                        //填坑法
        while (i < j) {
           while (i < j && nums[j] >= val) j--;
           nums[i] = nums[j]; 
           while (i < j && nums[i] <= val) i++;
            nums[j] = nums[i];
        }
        nums[i] = val; 
        return i;
    }
 
    void sort(vector<int>& nums, int left, int right) {
        if (left >= right)
            return;
        int mid = partition(nums, left, right);
        sort(nums, left, mid-1);
        sort(nums, mid + 1, right);
    }
    vector<int> sortArray(vector<int>& nums) {
        
        sort(nums, 0, nums.size()-1);
        return nums;
    }
};

int pattern(int l,int r)
{
	int i = l,j = r;
	while(i<j)
	{
		while(i<j && a[i]<=a[j])
			j--;
		if(i<j)
			swap(a[i],a[j]);
		while(i<j && a[i]<=a[j])
			i++;
		if(i<j)
			swap(a[i],a[j]);
	}
	return i;
}

void sort(int i,int j)
{
	if(i<j)
	{
		int mid = pattern(i,j);
		sort(i,mid-1);
		sort(mid+1,j);
	}
}

#if 0
#include<bits/stdc++.h>                       
using namespace std;                      
int a[10000];
int n;
void sort(int a[], int n) {
	bool flag = 0;
	int k = n-1;
	int last;
	for (int i = 0; i < n-1; i++) {
		flag = 0;
		for (int j = 0; j < k; j++) {
			sum++;
			if (a[j] > a[j+1]) {
				flag = 1;
				last = j;
				swap(a[j], a[j+1]);
			}
		}
		if (flag == 0) {
			break;
		}
		k = last;
	}
}
int main()
{
	while(1) {
		sum = 0;
		cin>>n;
		for (int i = 0; i < n; i++) {
			a[i] = rand() % n;
		}		
		sort(a, n);
		for(int i = 0; i < n; i++)
			 cout<<a[i]<<" "; 
	
	}
} 

#endif

#if 0                      //波浪排序 就上两种优化
#include<bits/stdc++.h>
using namespace std;
int a[100000],n;
void sort(int a[], int n) {
	int left = 0, right = n-1;
	int flag = 0;
	int last;
	while (left < right) {
		for (int i = left; i < right; i++) {
			sum++;
			if (a[i] > a[i+1]) {
				swap(a[i], a[i+1]);
				flag = 1;
				last = i;
			}
		}
		if (flag == 0) break;
		right = last;
		flag = 0;
		for (int j = last; j > left; j--) {
			sum++;
			if (a[j] < a[j-1]) {
				swap(a[j], a[j-1]);
				flag = 1;
				last = j;
			}
		}
		if (flag == 0) break;
		left = last;
	}
}
int main()
{
	while(1) {
		cin>>n;
		for (int i = 0; i < n; i++) {
			a[i] = rand() % n;
		}		
		sort(a, n);
		for(int i = 0; i < n; i++)
			 cout<<a[i]<<" "; 
	
	}
}  
#endif

class Solution {
public:
    ListNode* merge(ListNode* left, ListNode* right) {
        ListNode* result = new ListNode(-1);
        ListNode* r = result;
        while (left != NULL && right != NULL) {
            if (left->val <= right->val) {
                r->next = left;
                r = r->next;
                left = left->next;
            } else {
                r->next = right;
                r = r->next;
                right = right->next;
            }
        }
        if (left != NULL) r->next = left;
        if (right != NULL) r->next = right;
        return result->next;
    }
    ListNode* sortList(ListNode* head) {
        if (head == NULL || head ->next == NULL) return head;
        ListNode* pre = NULL;
        ListNode* fast = head, *slow = head;
        while (fast != NULL && fast->next != NULL) {
            pre = slow;
            fast = fast->next->next;
            slow = slow->next;
        }
        pre->next = NULL;
        ListNode* left = sortList(head);
        ListNode* right = sortList(slow);
        return merge(left, right);
    }
};

class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode* result = new ListNode(-1);
        ListNode* r = result;
        while (l1 && l2) {
            if (l1->val <= l2->val) {
                r->next = l1;
                r = r->next;
                l1 = l1->next;
            } else {
                r->next = l2;
                r = r->next;
                l2 = l2->next;
            }
        }
        if (l1) {
            r->next = l1;
        }
        if (l2) {
            r->next = l2;
        }
        return result->next;
    }
    ListNode* table[64] = {NULL};
    int fill = 0;
    int i = 0;
    ListNode* carry;
    ListNode* sortList(ListNode* head) {
        if  (head == NULL || head->next == NULL) return head;
        while (head != NULL) {
            ListNode* next = head->next;
            head->next = carry;
            carry = head;
            i = 0;
            while (i < fill && table[i]) {
                table[i] = merge(carry, table[i]);
                carry = NULL;
                swap(carry, table[i++]);
            }
            swap(carry, table[i]);
            if(i == fill) fill++;
            head = next;
        }   
         ListNode* result;
        for (int i = 1; i < fill; i++) {
            table[i] = merge(table[i], table[i-1]);
        }
        return table[fill-1];
    }
};

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode* result = new ListNode(INT_MIN);
        ListNode* r = result;
        ListNode* next;
        while (head != NULL) {
            next = head->next;
            ListNode* r = result;
            while (r != NULL && r->next != NULL && r->next->val < head->val) {
                r = r->next;
            }
            head->next = r->next;
            r->next = head;
            
            head = next;
        }
        return result->next;
    }
};

//全排列 
#if 0
#include<bits/stdc++.h>
using namespace std;
void fun(int a[],int k,int m)
{
	if(k == m)
	{
		for(int i=0; i<=m; i++)
			cout<<a[i]<<" ";
		cout<<endl;
	}
	for(int i=k; i<=m; i++)
	{
		swap(a[k],a[i]);
		fun(a,k+1,m);
		swap(a[k],a[i]);
	}
}


int main()
{
	int n;
	int a[100];
	cin>>n; 
	for(int i=0; i<n; i++)
	{	
		cin>>a[i];
	}
	fun(a,0,n-1);
	
}
#endif

1.KMP
/*KMP算法 
查询字符串a中 是否包含 字符串b    
ababcabcacbab
abcac
*/
    
void getNext(string str) {
	int k = 0;
	for (int i = 1; i < str.size(); i++) {
		while (k > 0 && str[i] != str[k])
			k = next[k-1];                               //精髓
		if (str[i] == str[k]) k++;
		next[i] = k;
	}
} 

int kmp(string s1, string s2) {
	int i = 0, j = 0;
	for (i = 0; i < s1.size() && j < s2.size(); i++) {
		 if (s1[i] == s2[j]) {
		 	j++;
		 } else {
		 	j = next[j-1];                          //需要感受
		 }
	}
	if (j == s2.size()) return i - s2.size();          //返回第一次匹配的的下标
	return -1; 
}

2.背包问题  
//     01背包问题  
// f[i][j]代表了 前i个物品的时候 容量为j的时候的最大的价值量，其中j必须是从v ...0的，因为每一个物品要选一次！！！ 

{
	
	int m,n;                 //m:背包的容量 n:物品的个数 
	cin>>m>>n; 
	int w[n+10];			   //每个物品的重量 
	int c[n+10];				//每个物品的价值 
	int f[m+10];             //f[k]代表 k个物品的时候，能装的最大的价值 
	memset(f,0,sizeof(f));
	for(int i=0; i<n; i++)
	{
		cin>>w[i]>>c[i];
	}
	for(int i=0; i<n; i++)
	{
		for(int v = m; v>=w[i]; v--)
		{
			f[v] = max(f[v],f[v-w[i]] + c[i]);
		}	
	} 
	cout<<f[m]<<endl;		
}


//完全背包问题
{
	int m,n;                 //m:背包的容量 n:物品的个数 
	cin>>m>>n; 
	int w[n+10];			   //每个物品的重量 
	int c[n+10];				//每个物品的价值 
	int f[m+10];             //f[k]代表 k个物品的时候，能装的最大的价值 
	memset(f,0,sizeof(f));
	for(int i=0; i<n; i++)
	{
		cin>>w[i]>>c[i];
	}
	for(int i=0; i<n; i++)
	{
		for(int v = w[i]; v<=m; v++)
		{
			f[v] = max(f[v],f[v-w[i]] + c[i]);
		}	
	} 
	cout<<f[m]<<endl;
}

3.最大上升 子序列 
/*给出 [4,2,4,5,3,7]，LIS 是 [2,4,5,7]，返回 4
*/

int fun(int a[],int n)
{
	int b[n];                    //截至到i 最大的上升子序列 的个数 
	for(int i=0; i<n; i++)
		b[i] = 1;
	for(int i=1; i<n; i++)
	{
		int max = -1;
		for(int j=0; j<i; j++)                        //找出前面比  此时的x 小的，并且 连续数最 大的   ~！！！ 
		{
			if(a[j] < a[i] && b[j] > max)
			{
				max = b[j];		
			}
		}
		if(max != -1)
			b[i] = max +1;
	}
	int maxx = 0;
	for(int i=0; i<n; i++)
		maxx = max(b[i],maxx);
	return maxx;
}

最大子数组和
4.{
    int a[] = {1, -2, 3, -4, 5, 6, -7};
	int n = sizeof(a) / sizeof(int);
	int max = INT_MIN;
	int k = INT_MIN;
	for (int i = 0; i < n; i++) {
		if (k > 0) {
			k += a[i];	
		} else {
			k = a[i];
		}
		if (k > max) {
			max = k;
		}
	}    
  }

//排序算法有 冒泡  / 快排/ 选择/堆排序/  归并 / 桶排序 /

//1.冒泡排序
#if 0
#include<bits/stdc++.h>
using namespace std;

void sort(int a[],int n)
{
	for(int i=0; i<n-1; i++)
	{
		for(int j=0; j<n-i-1; j++)          //
		{
			if(a[j] > a[j+1])
				swap(a[j],a[j+1]);
		} 
	} 
}
int  main()
{
	int a[1000];
	int n;
	cin>>n;
	
	for(int i=0; i<n; i++)
		cin>>a[i];
	sort(a,n);
	
	for(int i=0; i<n; i++)
		cout<<a[i]<<" ";
	
}
#endif 


//1.1 快速排序
 #if 0
#include<bits/stdc++.h>
using namespace std;
int a[1000];
int pattern(int l,int r)
{
	int i = l,j = r;
	while(i<j)
	{
		while(i<j && a[i]<=a[j])
			j--;
		if(i<j)
			swap(a[i],a[j]);
		while(i<j && a[i]<=a[j])
			i++;
		if(i<j)
			swap(a[i],a[j]);
	}
	return i;
}

void sort(int i,int j)
{
	if(i<j)
	{
		int mid = pattern(i,j);
		sort(i,mid-1);
		sort(mid+1,j);
	}
}

int  main()
{
	
	int n;
	cin>>n;
	
	for(int i=0; i<n; i++)
		cin>>a[i];
	sort(0,n-1);
	
	for(int i=0; i<n; i++)
		cout<<a[i]<<" ";
	
}
#endif

//2.选择排序

#if 0
#include<bits/stdc++.h>
using namespace std;

void sort(int a[],int n)
{
	int num;
	for(int i=0; i<n-1; i++)
	{
		num = i;
		for(int j=i+1; j<n; j++)          
		{
			if(a[j] > a[num])
				num = j;
		} 
		if(num != i)
			swap(a[num],a[i]);
	} 
}
int main()
{
		int a[1000];
	int n;
	cin>>n;
	
	for(int i=0; i<n; i++)
		cin>>a[i];
	sort(a,n);
	
	for(int i=0; i<n; i++)
		cout<<a[i]<<" ";
	
}
#endif

//3. 归并排序
#if 0
#include<bits/stdc++.h>
using namespace std;
int r[1000],r1[1000];
void merge(int s,int m,int t)
{
	int i=s,j=m+1,k=s;   

	while(i<=m && j<=t)
	{
		if(r[i]<=r[j])       	
			r1[k++] = r[i++];
		else
			r1[k++] = r[j++];
	}

	
		while(i<=m)
			r1[k++] = r[i++];
		while(j<=t)
			r1[k++] = r[j++];
				
	for(int z=s; z<=t; z++)
	  	r[z] = r1[z];
		

}
void sort(int s,int t)
{

	if(s>=t)
		return;
		
		int m = (s+t)/2;
		sort(s,m);
		sort(m+1,t);
		merge(s,m,t);
}

int main()
{

	int n;
	cin>>n;
	for(int i=0; i<n; i++)
	{
		cin>>r[i];
	}
	sort(0,n-1);
	
	for(int i=0; i<n; i++)
		cout<<r1[i]<<" "; 
			      
}
#endif

//4.堆排序

#if 0
#include<bits/stdc++.h>
using namespace std;
int a[100000];
int n;

void sift(int s,int t)
{
	int i=s,j=2*s;
	while(j<=t)
	{
	
		if(a[j+1] > a[j] && j<t)
			j++;
		if(a[i] > a[j])
			break;
		else
		{
			swap(a[i],a[j]);
			i = j;
			j = 2*i;
		}
	
	}

}

void sort(int n)
{
	for(int i=n/2; i>=1; i--)  
	{
		sift(i,n);
	}
	
	for(int i=1; i<n; i++)
	{
		swap(a[1],a[n-i+1]);
		sift(1,n-i); 
		
	}
}


int main()
{

	cin>>n;
	for(int i=1; i<=n; i++)
	{
		a[i] = n-i;
	}
	sort(n);
	
	for(int i=1; i<=n; i++)
		cout<<a[i]<<" ";
			
}
#endif

//基数排序

#if 0
#include<bits/stdc++.h>
using namespace std;
int head;
struct Node
{
	int key;
	int next;
};
struct QueueNode
{
	int front,rear;
};

void distribute(Node r[],int n,QueueNode q[],int m)
{
	int i = 0;                     							//默认为0   最后的next为 -1 
	while(1)
	{
		int key = r[i].key;
		if(q[key].front==-1)
		{
			q[key].front = i;
		}
		else
		{
			r[q[key].rear].next = i;
		} 
		q[key].rear = i;
		i = r[i].next;
		
		
		if(i == -1)
			break;
	}
	
}

void collection(Node r[],int n,QueueNode q[],int m)
{
	int k = 0;
	while(q[k].front==-1)
		k++;
	int first = q[k].front;
	int last = q[k].rear;
	head = first;
	
	while(k<m)
	{
		k++;
		if(q[k].front!=-1)
		{
			r[last].next = q[k].front;
			last = q[k].rear;
		}
	}
	r[last].next = -1;
}

void bucketSort(Node r[],int n,QueueNode q[],int m)
{
	for(int i=0; i<n; i++)
		r[i].next = i+1;
	r[n-1].next = -1;

	for(int i=0; i<m; i++)
	{
		q[i].front = q[i].rear = -1;	
	}  
	
	
	distribute(r,n,q,m);
	collection(r,n,q,m);
		
		
}

int main()
{
	Node r[1000];
	QueueNode q[1000];
	
	int n;
	cin>>n;
	
	for(int i=0; i<n; i++)
		r[i].key = n-i;
	
	bucketSort(r,n,q,100);	
	
	
	while(head!=-1)
	{
		cout<<r[head].key<<" ";
		head = r[head].next;
	}
	
}
#endif

//插入排序
#if 0
#include<bits/stdc++.h>
using namespace std;

void sort(int a[],int n)
{
	for(int i=2; i<=n; i++)
	{
		a[0] = a[i];
		int j;
		for(j=i-1; a[j] > a[0]; j--)
		{
			a[j+1] = a[j];
		}
		a[j+1] = a[0];
	}
}


int main()
{
	int a[100];
	int n;
	cin>>n;
	for(int i=1; i<=n; i++)
		cin>>a[i];
	sort(a,n);
	
	for(int i=1; i<=n; i++)
		cout<<a[i]<<" ";
	
}
#endif

//希尔排序
#if 0 
#include<bits/stdc++.h>
using namespace std;

void sort(int a[],int n)
{
	for(int d=n/2; d>=1; d/=2)
	{
		for(int i=d+1; i<=n; i++)
		{
			a[0] = a[i];
			int j;
			for(j=i-d; j>0&&a[0]<a[j]; j-=d)
			{
				a[j+d] = a[j];
			}
			a[j+d] = a[0];
		}
	}
}

int main()
{
	int a[100];
	int n;
	cin>>n;
	for(int i=1; i<=n; i++)
		cin>>a[i];
	sort(a,n);
	
	for(int i=1; i<=n; i++)
		cout<<a[i]<<" ";
}
#endif