LIS of Sequence

# 题意： 给你一个长度为n的序列a1,a2,...,an，你需要把这n个元素分成三类：1，2，3： 1:所有的最长上升子序列都不包含这个元素 2:有但非所有的最长上升子序列包含这个元素 3:所有的最长上升子序列都包含这个元素 # 输入格式： 第一行包含一个正整数n，表示序列的长度。第二行包含n个正整数a1,a2,...,an，表示序列中的元素。 # 输出格式： 一行，包含一个长度为n的、由1,2,3三种数字组成的字符串，第i个数字表示ai所属类别。 # 数据范围： 1≤n≤10^5 1≤ai≤10^5

The next "Data Structures and Algorithms" lesson will be about Longest Increasing Subsequence (LIS for short) of a sequence. For better understanding, Nam decided to learn it a few days before the lesson. Nam created a sequence $ a $ consisting of $ n $ ( $ 1<=n<=10^{5} $ ) elements $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=10^{5} $ ). A subsequence $ a_{i1},a_{i2},...,a_{ik} $ where $ 1<=i_{1}<i_{2}<...<i_{k}<=n $ is called increasing if $ a_{i1}<a_{i2}<a_{i3}<...<a_{ik} $ . An increasing subsequence is called longest if it has maximum length among all increasing subsequences. Nam realizes that a sequence may have several longest increasing subsequences. Hence, he divides all indexes $ i $ ( $ 1<=i<=n $ ), into three groups: 1. group of all $ i $ such that $ a_{i} $ belongs to no longest increasing subsequences. 2. group of all $ i $ such that $ a_{i} $ belongs to at least one but not every longest increasing subsequence. 3. group of all $ i $ such that $ a_{i} $ belongs to every longest increasing subsequence. Since the number of longest increasing subsequences of $ a $ may be very large, categorizing process is very difficult. Your task is to help him finish this job.

The next "Data Structures and Algorithms" lesson will be about Longest Increasing Subsequence (LIS for short) of a sequence. For better understanding, Nam decided to learn it a few days before the lesson. Nam created a sequence $ a $ consisting of $ n $ ( $ 1<=n<=10^{5} $ ) elements $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=10^{5} $ ). A subsequence $ a_{i1},a_{i2},...,a_{ik} $ where $ 1<=i_{1}<i_{2}<...<i_{k}<=n $ is called increasing if $ a_{i1}<a_{i2}<a_{i3}<...<a_{ik} $ . An increasing subsequence is called longest if it has maximum length among all increasing subsequences. Nam realizes that a sequence may have several longest increasing subsequences. Hence, he divides all indexes $ i $ ( $ 1<=i<=n $ ), into three groups: 1. group of all $ i $ such that $ a_{i} $ belongs to no longest increasing subsequences. 2. group of all $ i $ such that $ a_{i} $ belongs to at least one but not every longest increasing subsequence. 3. group of all $ i $ such that $ a_{i} $ belongs to every longest increasing subsequence. Since the number of longest increasing subsequences of $ a $ may be very large, categorizing process is very difficult. Your task is to help him finish this job.

Print a string consisting of $ n $ characters. $ i $ -th character should be '1', '2' or '3' depending on which group among listed above index $ i $ belongs to.

1
4

3

4
1 3 2 5

3223

4
1 5 2 3

3133

The next "Data Structures and Algorithms" lesson will be about Longest Increasing Subsequence (LIS for short) of a sequence. For better understanding, Nam decided to learn it a few days before the lesson. Nam created a sequence $ a $ consisting of $ n $ ( $ 1<=n<=10^{5} $ ) elements $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=10^{5} $ ). A subsequence $ a_{i1},a_{i2},...,a_{ik} $ where $ 1<=i_{1}<i_{2}<...<i_{k}<=n $ is called increasing if $ a_{i1}<a_{i2}<a_{i3}<...<a_{ik} $ . An increasing subsequence is called longest if it has maximum length among all increasing subsequences. Nam realizes that a sequence may have several longest increasing subsequences. Hence, he divides all indexes $ i $ ( $ 1<=i<=n $ ), into three groups: 1. group of all $ i $ such that $ a_{i} $ belongs to no longest increasing subsequences. 2. group of all $ i $ such that $ a_{i} $ belongs to at least one but not every longest increasing subsequence. 3. group of all $ i $ such that $ a_{i} $ belongs to every longest increasing subsequence. Since the number of longest increasing subsequences of $ a $ may be very large, categorizing process is very difficult. Your task is to help him finish this job.